The right way is entirely dependent on what limitations you want to place on your users.
WordPress ships with a library called plupload. This is what powers the multi-file uploader in core, and it’s available to create your own upload tools as well. The beneficial feature of plupload is the ability to chunk files on the client side before uploading them.
Essentially, plupload lets you split large files up on the client and upload much smaller files to the server. As a result, your server is more responsive (doesn’t have to handle very long requests). On the downside, these features are difficult to implement in older browsers (read: Internet Explorer) and require stand-ins (read: Flash or Silverlight).
Using plupload isn’t a WordPress question, so if you go this route I encourage you to open new questions on SO.