Why your current code fails
Your always getting the content of the first page, because the string of parameters passed to query_posts being encapsulated in single quotes prevents variables (as well as escape sequences for special characters other than $) to be expanded.
query_posts("post_type=videos&posts_per_page=9&paged=$paged"); would take care of that problem.
query_posts('post_type=videos&posts_per_page=9&paged='.$paged); would also.
And finally, passing an array of mixed arguments instead of a URL-query-style string would as well.
That being said though, you should not use query_posts at all:
How it should be done
As per your comment, you attempted to use get_posts.
That is a very useful function indeed, but not the correct way to go if you want to use a WordPress-Loop thereafter.
get_posts returns an array of post objects – the WP_Query object’s posts property. But only that one property, without all the other goodies and methods, that WP_Query provides.
Hence, to go with your above code snippet, do something along the lines of this:
<?php
$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
$args = array(
'post_type' => 'videos',
'posts_per_page' => 9,
'paged' => $paged
);
$your_query = new WP_Query( $args );
if ( $your_query->have_posts() ) {
/* The Loop */
while ( $your_query->have_posts() ) {
$your_query->the_post();
// do something
}
} else {
echo 'Sorry, no posts found.';
}
?>