Search for Surety Bond for more bonding info.
http://en.wikipedia.org/wiki/Surety_bond
As far as insurance. A general liability policy is all you need. The smallest commercial liability policy is either a $125,000 or $250,000 I think.
I've got $1,000,000 for about $300 per year with Allstate. Allstate has a "Locksmith Policy" that is more suited for our business than a standard policy. Not all agents are familiar with it, so you might have to get them to call someone for help.