This is a big problem. To find a place is easy. Of course all these places are for tourists. They have a web site, advertising and everything.
A really nice place to see traditional fado is a place where you feel like you are in 1970.
I recommend the Tasca do Chico it is a traditional place where I used to bring my parents and friends when I lived in Portugal.
Another great place to go to find great Fado is Bairro Alto. Walk around the streets and check inside the small doors to try to find traditional Fado. Usually the tascas have a different atmosphere. You can experience a real Portuguese night.
Fado has some rules. In a place to listen Fado you must be quiet, noise and conversation must be avoided in this place. At the end of the music you must hit the glasses (like in the cheers) instead of clapping.