Each faction has three auction house locations. The locations are linked (they were connected in patch 1.9 and Classic will begin with patch 1.12) which means you will access the same list of items for sale regardless of which of your factions auction house you go. The Auction Houses are faction-specific though, so you will only be able to trade with other alliance players on the alliance AH.
In addition to the factioned Auction Houses, there is a set of Neutral Auction Houses that both factions can access. These auction houses have a much higher cut, and they are quite a bit more annoying to get to, which means they are not used particularly much. They represent the only way to move items or gold across factions, however, so they do fill a niche.
In Darnassus The Auction House is the first that most Night Elf players will have access to. It's located on the north end of the Tradesman's Terrace, right beside the water. It's an open building with two levels, with auctioneers on each.
The Ironforge Auction House is located in the commons one the outer ring of Ironforge just between the two tunnels that come in from the gates of Ironforge and Dun Morogh. Players have to walk into the Commons, then turn around to find the AH on the same side of the bridges as the gate.
The Third Alliance Auction House can be found in the aptly named Trade District of Stormwind. It is in one of the buildings directly ahead of you as you enter the city as marked on the map here.
Neutral Auction House Locations
There are three Auctioneers spread around Booty Bay. One is in the house closest to the inn on the lowest level, and one is just by the bank on some crates, the last one is on the north end on some crates. The positions are all marked on the screenshot below.
In Tanaris you can find Auctioneer Beardo in Gadgetzan in the first building on the right if you enter the city from the south.
The final Neutral Autction House is in Wintersprings. Auctioneer Grizzlin is in the building with the telescope on top of it in Everlook. This building also houses the bank here, which makes it convenient.