Registration of company/business name is as simple as ABC especially when you know the procedures involved, some peoples are of the notion that company’s registration is the sole responsibility of legal practitioners, but it is not so, it only involves a simple procedure which any body can follow.
The procedure is very simple
If you live in Lagos go to the office of the Corporate Affairs Commission located at Yaba  get the name search availability form for N200 (two hundred naira only)fill it with two name suggestions (that is your proposed business name, you have two options for this)
Fill it appropriately and submit wait for two or three weeks then come back for your result, if the name is approved, pick another form( business name registration form) at the cost N250 which is the cost of your file, fill it and submit with N4000  which is the cost of the certificate and two passport. come back in two weeks or less to collect your certificate.
That is just it, if you follow these steps as explained you will have your company certificate. so no need paying N20,000 to any body to do it for you,
But as simple as this procedure may sounds there are still some other things that must be taken into cognizance, first I have been in this business of company registration for a long time and I discover that many peoples that apply for their company registration end up not getting their certificate, the reasons are obvious and simple, CAC places a lot of importance to details the as it appear your form. So failure to fill these information accurately means your application may be disqualified 
This is one of the reasons why many people complain of not getting their certificate after passing through these so called tedious procedures.
But no problem see the example of how to fill these forms all scanned and explained here http://www.3in1infoproduct.com.

what if am not based in lagos? i plan on registering a business name and when i made a few contacts a lawyer told me N100,000
It really shocked me but i later got someone else to do the job for N15,000 didnt know it was that cheap.
So, if am not in lagos how do i go about it?

@ mike eliso

great job, But i should first inform you that it looks like its been a while you have been to any cac offices. Prices have changed. Filing fees for business names in cac is now 5000 naira not 4000 naira again. Also you forgot to inform them that you now have to go to the magistrate to sign before you can pay filing fees. So confirm all that and change your values. Thanks. For express business names, limited and incorporated trustees like ngos,church,clubs and so on. Check our signature for our website and contact, Nice job bro.