I've seen Echidnas in Tasmania, Queensland and Western Australia, but not NSW or Victoria (I haven't been to the other states yet). They aren't really an animal you can specifically go look for, you just have to come across them fortuitously. For Platypus you can sit by a river where they occur and you'll likely see one eventually, but you could sit down on a log in Echidna territory for a week and still not see one walk past. Even though Platypus are the more famous ones, seeing an Echidna is much better.