Update 2016: It now appears to be possible to use non-Chinese phone numbers to create Baidu accounts, see this page.
Once you're logged into Baidu you need to find their LBS (location-based services) cloud and go to the control center there:
http://lbsyun.baidu.com/apiconsole/key
There you click "Create a new app/key" 创建应用(0/20) (orange button). In the popup you give it a name and then in your case probably select "for server". The following list of checkboxes is for the things you want to BLOCK for your key. If you want access to everything then tick NOTHING (took me a while to figure that out, I always ticked everything...)
For server keys you can select an IP based whitelist for users, you would enter the addresses of your servers there. I'm not sure about the other (sn) option.
When you click Confirm the new key should appear in the table, copy & use it.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…