from a html page have a form that the user can select the file to upload. It is then passes to your php script and handled through the $_FILES (see php.net for more info). if all is in order you move_uploaded_file to your folder of choice (again see php manual). Then unless you have unlimited bandwidth you'll need to convert these to a format that uses less bandwidth and memory e.g FLV. Mencoder, FFMPEG, etc will all do this for you.
After that its a matter of having your users select which video to play and then embedding it <embed> or <object id> . You can look these up. ALthogether about 4/5 pages of php and html should cover the whole process. :P