[eluser]m4rw3r[/eluser]
It would probably be the same way you store images which users have uploaded.
Store them in a certain directory (maybe also subdirectories for each user) and then store the filename (and subdir name) in the database.
Then you also need a user_id column, to fetch the owning user / find all videos for a certain user.