Hi Bilal and welcome to the Local Search forum.
The most common way to advertise is through Pay-Per-Click, where you only pay when someone clicks on your advert and your adverts only show for searches that you specify.
Often you will find that sites choose to run Pay-Per-Click adverts from major companies rather than deal with advertisers directly. You need to find out if the sites your are targeting run their own adverts or not. If they run their own adverts then they should have details of how to advertise on their site (giving them a ring might help you understand their options), if not you'll normally see 'Ads by Google' or something similar near the adverts.
The big 3 have huge coverage in the US, they are Google (AdWords), Yahoo (Yahoo Search Marketing) and AdCenter. You can go directly to these providers and create your own adverts or you can use an agency to do this for you (depending on how confident you are and whether you don't mind paying extra for someone to do it for you).
There are other PPC systems that are offered on some 'Yellow Pages' type sites, so if there is a business classification that fits your business type you may want to look at the larger Yellow Pages and Local Search providers.
Other options include fixed-price featured listings right through to banner advertising. I would suggest sticking to PPC until you get more information on how that's working out. One area of PPC that can be very handy is the ability to target by specific sites, so if a site you think would work for your adverts has adverts by Google you can set up a campaign to show on that site (you cans et up many different campaigns).
If you are targeting locally then there are different ways to do this. Local Search sites usually have this covered very easily, you say what you want to cover and where and you'll only show for the things that interest you. PPC networks can involve more work to set up correctly, this would involve adding place names to your search terms and possibly using IP targeting.
To make sure you make the best use of your time and money it may be an idea to think of how people will find sites that offer services similar to yours. Will they simply go to a search engine? Are there a few sites that attract the type of people you are looking for?
Often a good place to start is at Google, do quite a few searches for the things that you think people will type when looking for your services and then take a note of the sites that appear in the 'free' or 'organic' listings. If a site appears often for your search terms it may be a good idea to see what advertising options they offer (as long as they are targeted to relevant pages on their site).
Often it pays to advertise directly on search engines as that is where many people will start out.
However, there are many business types that benefit from advertising on Yellow Pages and Local Search sites. Local companies often find their target audience choose business directories above search engines as people have come to realise that search engines list far more than just companies (hence the reason search engines are developing their own Local Search offerings).