To get off some lists, you don't need to do anything; for others, you need to make some changes and prove that you've made those changes. The procedures are as varied as the lists themselves:
Your IP may automatically drop off the blacklist, or timeout, after a specific length of time, which may be a couple of weeks.
You submit a form on the list-holder's website.
You make adjustment to your list management practices to tighten security and make it hard for spammers to use your server, then apply to be removed from the blacklist.
Change your ISP. If the dynamic IP addresses your ISP assigns you are compromised, changing your provider may be the most efficient way to get off and stay off blacklists.
When approaching an entity that's placed you on their blacklist, start with the assumption that something you did caused your domain to be added. A belligerent, take-me-off-now attitude can land you on a permanent blacklist with no chance of getting off it.
Credits
In short, you could do this yourself, instead of paying someone to do the same.