You're asking a large question. This is an area that could easily keep someone busy full-time. I did a search at Google for "search engine submit tutorial". Here's the first site returned: http://searchenginewatch.com/webmasters/
Looks like a decent place to start your education.
To answer your questions;
Yes, you can do it yourself in many cases. Some are free, others cost real money. Go to each & look for their instructions.
Yes, it can be very time-consuming.
In my opinion, if you absolutely need your site listed ASAP, do it via software. If you can wait, read as much as you can on the subject & tweak (& tweak & tweak &....) your site.
Most search engines are very complicated so the people who make the search engine submition software usally have to pay for the info to be able to make the software work. I have seen some out there that actually use hacking techniqes to submit you site to the search engine server. But thats from my experiance. Hope that helps.
Thanks to all for your comments, links and information. Based on my experience level ("baby" beginner) and the amount of time I have for this, I think I'll be better off just paying for the software/service.
Can anyone give me a good recommendation, based on quality of service (ie., how often your site was found after you used it) and cost ? All recommendations appreciated.