I've been plugging along this past week with Archaeology and I wanted to share my findings so far. At this point I'm sitting at 350, so I feel like I've got a pretty good handle on how it works. Obviously these things can change before the expansion launches and sometimes do. Let's just call this a compilation of information and tips that may be useful to future Archaeologists.
First - the trainer is in Stormwind. If there's another trainer, I'm unaware of it. But honestly, if you're going to learn Archaeology, how can you NOT study with Harrison Jones??? Stormwind is shaping up to be the primary Cataclysm hub, so it's perfectly valid to stake it out as your new home. Harrison teaches you each rank of Archaeology and the starter ability: Survey. You only need to return to him every 75 skill points to pick up the next rank. He can be found in the Stormwind Library, surrounded by a gaggle of adoring students (love it!).
You have four dig site spawns on each continent and you can hop from one to another based on proximity to your starting location. You can also prioritize based on racial type if you happen to be working on a particularly special object. It shouldn't be too hard to figure out most locations. Stranglethorn is predominantly troll ruins, Badlands has mostly dwarf ruins. The one I find most difficult is the generic "fossil" artifacts. It's hard to tell when an area will harbor fossil ruins. So far Un'Goro Crater seems to be a reasonably safe bet.
Occasionally you end up getting "keystones", which are like wild cards that let you substitute missing fragments (aka finish an artifact faster). On larger artifacts such as rares you can use multiple keystones. I tend to save mine up so I have plenty for building rare objects. Collecting 100 fragments is less painful when you can "sub" 20 or 30 of them!
Something new I discovered this week is that Outland artifacts require 45 fragments instead of the 35(ish) fragments that Kalimdor and Eastern Kingdoms tend to need. This can slow down your leveling progress, especially if you don't have keystones. Which you won't when you you first arrive in Outland. However, you have the option to stay in old world zones. You can still build artifacts and get skill points without switching to Outland. Your progress may even be faster since you typically need less fragments to complete an artifact and you should have a supply of appropriate keystones built up. Alternately you may decide you prefer a change of scenery after spending so much time zigzagging across the vanilla zones.
The experience gain is pretty major right now. My druid was about halfway through level 80 when I picked up Archaeology. At 350 skill she is just shy of level 84. For those counting, that's 3.5 character levels I've gotten just from picking up fragments. At least half of that is non-rested XP since I ran out somewhere around level 82. Since I still have 175 more points to go, I have no doubt I can get to 85 just from Archaeology XP. I fully expect this to be nerfed before launch. Even with a reduction in XP I think Archaeology will be a nice change of pace for those leveling up alts in Cataclysm and not wanting to do the same rounds of quests 2/3/4 times. Just something to keep in mind if you get bored and want to switch it up with something new.
I did a brief time test to estimate how long it takes to complete an artifact, including travel. This was a short trial, just 80 minutes tracked. But I completed four artifacts in that time, so the average is around 20 minutes per artifact. My test was in Kalimdor, these numbers may be a bit higher for Outland. The vanilla zones have more flight paths in them now than the expansion zones do, which helps travel time. This also doesn't take rares into account, they obviously take longer.
At this point I've unlocked four rare items and one epic. I'm still working on a rare Orc artifact, so I don't know what that one is yet. Each of these artifacts takes about 100 fragments to complete. From my experience so far, I'd estimate that around 1 in 10 artifacts you unlock will be a rare or better. I've completed 55 artifacts and 5 of those have been rare or epic. Here are some screenshots I took of them:
Unfortunately I already learned the wee dino pet item, so I don't have that to show. My daughter insisted on seeing the little guy :) The druid/priest statue puts a green spotlight on you that lasts about 10 seconds and is on a 1 minute cooldown. The wind chimes are not yet implemented and the clockwork gnome is just a pet.
That's all I have for now in terms of Archaeology discoveries, feel free to post any questions you might have in the Comments!