There are any number of screen recording programs you can use to capture the usage of the software (see the above posts for several links and hit Google for more). The trick with this sort of thing is to have the right narrator.
I've created at least two presentations like this and I simply copied the ones I've seen on other sites that appealed to me. This lead me to the following sequence (which seemed to work well):
1/ The voice over must be aimed at the target audience. So write a script that covers all the points you want to cover, grab someone who would be a typical user of your product and let them point out what they don't understand or is not important to them (the power users who want the more advanced features will go to your FAQ anyway). Adjust and trim your script appropriately.
2/ Find someone with a calm and friendly voice (preferably female) to do the voice over for you. I know that sounds sexist but most people (males and females) respond better to a calm female voice than to a male voice (Why do you think that is the default voice for most GPS units). You really need to record people reading from a script and then listen to the recordings rather than base it off a natural voice - there can be major differences.
3/ Run through the demonstration with you controlling the software and the narrator reading in the background. You need to figure out where pauses are required so the software can catch up or you need to wait for the explanation to finish before moving to the next feature. Non-verbal cues are good here - a flat palm to indicate a pause, thumbs up to indicate a continuation and simply waiting for speech to finish before moving to the next feature. Run through this at least twice and you should be ready to record for real.
4/ Do the final version in a noise free environment. After hours if this is for a corporate job or very early in the morning on a weekday if it's for your own project. You can get very good quality without a sound proofed room.
5/ You need to capture the screen as well as record the audio (see above for tools). Merging and synching the two can be done with tools available by default with a modern OS (iMovie or Windows Movie Editor) and posting it online is almost automatic (send to YouTube and embed the video in your site - hosting and bandwidth of the video is no longer your problem).
I hope this helps. Outsourcing this for a product demonstration seems pointless, costly and time consuming when you can do it yourself in 2 or 3 days and see the results immediately.