You dont need to be licensed to be bonded. A bond assures the client they will be reimbursed if contractor fails to complete the job.
It is not the same as insurance.
The first step
is to contact the small business division in your state government. Often, they provide help to start your own business. They will point out the licenses that might be required, taxes, etc. Many times they offer classes, social networking, etc. I think so many people overlook this resource. 99% of the consulting I have done has been thru social/business networking.
The next step is limiting your personal liability. This is done via an LLC or Inc. (depends on your state). This way you protect your personal assetts (house, car, savings) from litigation. In addition it will help you obtain lines of credit.
One thing I can tell you: Its easy to start a small side business. Its alot more complicated to do it correctly.