Videos plugin relies on OAuth plugin for authenticating to web services. You'll be invited to download and install the plugin in Videos plugin settings.
Once the plugin is installed, the first thing you will want to do is configure a video gateway that you want to use. We currently support YouTube and Vimeo :
craft/plugins/videosfolder by the one that you have downloaded.