Which Settlers of Catan expansions are recommended?
The two biggest expansions for Catan are Seafarers of Catan and Catan: Cities and Knights.  I previously asked the question, "How is gameplay improved in the Cities &amp; Knights Expansion?" recently before buying it myself.  I would check out the answers there for some other opinions on that expansion.  There is also a third expansion, Catan: Traders &amp; Barbarians, but that isn't as popular.

Seafarers of Catan

This was the first expansion for Catan.  The expansion expands the size of the board and gives you the ability to have islands separate from Catan.  The game comes with a number of different scenarios and the ability to create maps with random landmasses.  (Random maps on Seafarers is a favorite of one of the people I play with, and how we usually play.)  Besides adding boats which are roads going across the water, and a pirate to act as a robber, Seafarers doesn't significantly increase the game.

Catan: Cities &amp; Knights

Cities &amp; Knights was the second expansion for Catan and take the base game and builds up on it.  Three commodities are introduced to the game: Coin, Paper, and Cloth.  Cities, now instead of producing two resources, produce a resource and a commodity for ore, wood, and sheep.  The development cards are not used and progress cards in three colors are now used.  Progress cards are gained by developing your cities, and can't be bought.  You use the commodities to upgrade your cities through different levels to increase the speed of you earning progress cards.

Knights also move from being cards to being tokens on the board.  In addition, every so many turns, the barbarians come and attack Catan.  All active knights defend, and if Catan wins, the person who helped to defend the most gets a victory point.  If Catan looses, the person who helped the least, looses a city.  A third event dice determines when the barbarian moves or when progress cards can be generated.

All of this increases the length of the game and makes Cities &amp; Knights plays slower.  It's a much more strategic game with Cities &amp; Knights.  The progress cards also give you a lot of different options.  A number of cards directly harm other players, while benefiting you.

Catan: Traders &amp; Barbarians

This is the one I haven't played, but I do know it adds a lot of different scenarios and variants to Catan you can play with.  It includes the Catan Event Cards, and Settlers of Catan: The Great River.  (As a side note, I know my local game store carries The Great River as a separate expansion.)  The wikipedia article on this expansion has a lot of information available about it.

5-6 player Extensions

The main game and each expansion, has a 5-6 player extension for it that lets you play 5-6 players.  I have extensions so I can play the main game or Seafarers but have never actually had 5-6 people to play it.  Friends of mine speak very highly of playing Catan with more people though.  Adding more people does slow the game down though and if you play Cities &amp; Knights with 6 people, your looking at a very, very long game.

Recommendation

I love variety when playing games, and I find Seafarers adds a lot of variety that makes each game different.  You get this with playing random maps with the core game, but random landforms really diversifies what's going on.  We've had games with large landmasses or narrow landmasses.  If you want to break out of the standard Catan island, this is the expansion for you.  I can also speak highly of Cities &amp; Knights.  It's a different type of game, but adds a lot of depth and if your looking for that, get it.  No one has recommended Traders &amp; Barbarians to me yet, so I would say the jury is out on that one for me.  I would suggest both the other two expansions first, and get Traders &amp; Barbarians if your still looking for more Catan.

Finally, I would get the  5-6 player extensions on as need basis.  If you at least get the core game extension, you can at least play Catan if you have more people then usual.