Are there actually "maphacks" out there?
Yes. You can find them rather easily by googling - some of them cost money, so the authors want lots of people to find out about them.
I don't see how this is possible..
Understanding why this is possible (and why Blizzard cannot prevent it) requires a basic understanding of how peer-to-peer games (like Starcraft) work. I've written a fairly comprehensive answer regarding that here.
What are tell-tale signs of someone using them?
The most common method of detecting hackers is watching the replay, and seeing if your opponent selects any units he can't actually see. Since this is impossible without maphacks, that would mean he's maphacking.
Another, less reliable method is to watch the opponent at the start of the replay. Often, unknowledgable maphackers will center their screen on your base at the start of the map, or multiple times throughout the match, before they ever actually "discover" where your base is.
Of course, both of these things can be avoided by the maphacker, so neither is fool-proof.
How do you report players using them?
Click on "Report user" in Battle.Net and post the replay, with an explanation.