jackgordon is talking about the same thing as you are. The 'Sponsored Link's' you are referring to are in fact AdWords ads.
Please take a look at the page below, and follow the links to learn more about AdWords.
About AdWords:
[adwords.google.com...]
If I may be very straightforward with you, I would suggest that you spend a bit of time in the (free) AdWords Learning Center before you start an AdWords account. This will help to get you started on the right foot, and avoid frustration as well wasted time and money.
Please be aware that AdWords can be an extremely effective way to send targeted traffic to your site - but it does have a learning curve and takes real time and effort to use effectively.
AdWords Learning Center:
[google.com...]
AWA
This is more to protect yourself & be able to identify & compare which agency is better than another and how their offerings differ.
regarding recommendations, I would pick a company that has a good track record, preferably a sizeable agency. Read through testimonials on their website. Find an agency in your city or within your target market as they have a better idea of the day to day changes in market conditions. See the offers they have and see how it fits in with what you're after...
Hope that helps.