Tapping would have to be done at the handset level, unless your tapper has either some kind of govenment level access at the network operator end, or quantum levels of decryption power, in which case your possible phone tap is the least of your worries.
Assuming its a local tap, you can solve this by downloading the latest ROM for your phone and flashing it with it. Doing this is like formating a PC, you wipe everything and start again. You can also replace the "system restore" ROM image as well, just to make sure there isn't anything lurking there waiting for your next factory reset.
In terms of how it works, generally the simplest method is to get hold of your phone, and set a "prefix" on it, so whenever you dial a number, it dials this other number first. They just put in a number for a simple routing system which connects your call. Looks totally normal to you, but because its now running through the routing number, they can listen in. A variation of this scam is used, but they use premium numbers instead, the objective being to get cash rather than to listen in.
Long story short? The best security for your phone, after a screen password, is to never leave it where others can get to it.