Enjoy yourself. If you, like many/most, get your first toon to maximum level (or before) and go back and start another, it will never be quite the same. Don't rush. See the sights. Read quest text. Enjoy the lore.
You can get by without Auctioneer for a while. If you never buy upgrades (I wouldn't suggest it unless you /know/ you can afford it), you won't need Auctioneer to keep you from being ripped off. What you'd miss out on is that some things (cloth - types depending on server, small eggs, and some others - also depending on server) are "worth" much more than similar items. You'll definitely want it before your gathering professions start coming in, as you'll be entering a very competitive, unregulated, market (as they say in poker, if you can't spot the mark when you sit down at the table, the mark is /you/). It's relatively complicated, but worth the investment of time. BTW, the newest version has a "quick scan" option that, if you have a good/fast connection, significantly reduces time for scans, which increase in value the more often they are done.
As soon as you can, get skinning and either mining or herbalism (not both because you can only track either minerals or herbs at any one time). Enchanting (specifically /dis/enchanting, might be even better, but I don't recommend it if you're new to the game. Sell the proceeds on the auction house.
Don't ignore cooking and fishing. Don't spend so much time on them that they become boring, but some time invested is time well spent (I got many levels of fishing waiting for boats, which is dead time otherwise).
Be ready for combat, especially, to get a little boring. For a long time, all melee and all casters are relatively similar. It's not until past level 20 (or beyond) that classes gain the abilities that distinguish them and make each unique and fun.
Don't waste time killing random creatures for experience. Questing (and killing the things that stand in your way) is both less repetetive and a better use of your time. Unless you're killing things specifically for profit measured in money, either for what they drop or to skin them).
Don't forget the paladin-specific quests when they come along. It's part of the lore that gives the class its flavor and, for me, a big part of the fun. For a long time, it was sitting on the charger that really gave the feeling "I /am/ a paladin - I passed the trials and now I'm ready to wield the light". Mind you, if you're a blood elf, your lore is a bit different...