On the wall with drywall in front of the external wall, if that external wall is concrete you may have to use a wall anchor such as a tapcon or something similar to secure the rack to the wall. For more details, check out this question of me wanting to do the same thing.
For the drywall only wall, you can get by with basic drywall anchors, if you're not (or can't because of location) drill directly into a stud behind the drywall. This is because screwing directly to just drywall alone isn't really secure, and a not so soft 'tug' or multiple tugs may loosen your screws over time, sagging your racks, looking awful (you may have seen that before).
Anchors prevent this, in different ways. Some expand when the real screw is screwed end, others have wider threads. As long as you use an anchor with a decent weight rating (25lbs should be fine, no one is doing chinups off of your towel rack), it'll be around for a while.
I'll also say follow the directions provided with the anchors. Some require a pre-drilled hole, some don't. The ones that do usually provide
A drill bit
Instructions for the specific size hole to be drilled, then they can be pushed or gently hammered into the hole.
After that, screw the screws for your rack directly into the anchor. You may have to use the screws that came with the anchor or the size screw that the anchor instructions specified, or you may get away with the screws that came with your rack. If those screws are the 'pretty' ones or will be seen when the rack is installed, you may want to get anchors that are sized for screws close to the ones you'll be using.
This sounds complicated, but it's really not. The main thing is attention to detail and prepwork, as mentioned above. My guess is that from all the trouble you went through to get the old ones off, they might have done the same thing.