Pick a program. If you travel a lot, and have a laptop, get a program that runs on your laptop. If you don't have a laptop, and often use other people's computers, use one of the many websites that let you track your contacts online. If you need to do business away from a computer, completely, use a smart phone.
Make sure it has keywords, notes, and hopefully a conversation history. This is the difference between an address book and a contact-manager. A good contact manager will let you keep track of past phone calls, emails, conversations, including a date. You may hear from someone after two years of not speaking, and be able to pull up your notes and remind yourself what happened last time you spoke.
Try to find one with reminders. It is SO nice to punch a future date into your computer, and tell it to remind you to do something on that date.
Whichever one you choose, know it well. Spend a few hours really getting to know it. Then it will be effortless for years to come.
Keywords: Multiple keywords are the most important thing in your database. Every person in your address book should have a few words attached to their record like “drums, webdesign, percussion” or “agent, clubowner, songwriter”. Some people will only have one word there, some will have a list of the 25 instruments they can play. This comes in the most handy when you need to find “drums” in Texas, or you're trying to remember the full name of that webdesigner named “Dave”.
Notes: You need a big text area next to their contact info, where you can type anything you want. Type notes from your conversations. Cut-and-paste emails they've sent you.
Mail-merge: Mail-merge is what they call it when you write a form letter, and it puts the person's name in each letter, sending it separately, instead of sending everyone something that says “Dear Music Industry Professional” or “Hey everyone!”. You can even use these on a small level. Sometimes you need to email ten guitarists to see who wants a gig. Mail-merge would let you easily personalize those ten emails.
What program? I don't know. I used to recommend some, but times change so fast, new things coming out every month, old things disappearing, so instead you're just going to have to find one yourself.