Yep mate, it's banned. As of today you won't find a single copy of Grand Theft Auto: San Andreas, the PS2, Xbox and PC version in Australian shops. The Office of Film and Literature Classification said in a statement sales of the game are outlawed and they have stripped it of its official classification after learning of the explicit content.
Revocation of a classification means the computer game cannot be legally sold, hired, advertised or exhibited in Australia from the date the decision is made.[29 July 2005]
So if you happen to live in Aus and didn't buy the game yet, then your out of luck. Just remember that this doesn't mean that Liberty City Stories or any other new Grand Theft Auto will be banned in the country. San Andreas was only banned due to the fact it had sexual content on it.
Take 2 has just released a press release confirming the ban. They also mention that the European version's rating won't be affected in any way and will keep it's 18+ rating.