Be careful. There's a lot of snake oil out there.
If anyone promises results, they are lying. It's always a "best efforts" game.
Also, be wary of any blackhat tactics that some may use. Not all blackhat tactics are bad, or will get you banned, but you need to know your stuff very well in order to make those distinctions.
Onsite SEO is very easy for small sites. Nothing special there.
Offsite SEO is the harder part and requires much more effort. Think in the order or orders of magnitude more effort. This is the most important part.
Read up on link building, but don't take too much of what you read too seriously. Get the big picture first, then figure out the details on your own so that your SEO strategy fits your needs/budget/time.
This isn't particularly for you, but I've outlined some SEO tactics for software authors in some posts on
Robosoft. This
post talks about offsite SEO. If you have a blog, you can do the same thing by syndicating it through RSS.
For actual SEO services, everyone that I personally know that is good at SEO charges a lot. I certainly can't afford them.
Before you spend money, make sure to look into the company/individual and look for any case studies and follow up by checking them out. Some people will claim all sorts of things -- make sure that they aren't lying or stretching the truth.