I had always assumed that in the beginning of the game, you are captured trying to cross the border into skyrim from cyrodiil. I recently started a new playthrough, though, and followed Ralof back to Riverwood. I stayed by him to listen to him speak. He mentions that the Imperial ambush that swept us all up happened just outside of Darkwater crossing, which is nowhere near any provincial border. However, the horse thief I was in the cart with did mention that I was caught while trying to cross the border. The only border I could see that he would be referencing is the Hold border between the Rift and Eastmarch. This border does seem to run very close to Darkwater crossing, so it would make sense, or am I missing something here?

There's no hard evidence that we were crossing a border at a all. Ralof may simply be repeating something he heard somebody else repeat, who got it from somebody who didn't know what he was talking about. It could be nothing more than a rumor. It's up to us to decide why our characters are on that wagon.

I would highly agree with you on this, I never once crossed any border in skyrim, except for one mod that required it.

http://elderscrolls.wikia.com/wiki/Gates_to_Cyrodiil

They are unmarked locations, one of which is known as the pale pass, which you might know from Oblivion.

As said, you are 100% known to be crossing the border, he is just guessing considering the location, it is up to the player to decide if he is right or not.

Ralof says they were on their way to Darkwater Crossing when they were ambushed, but he doesn't mention where did they set out from. Also, he doesn't mention where exactly they were ambushed.

It's quite possible that Ulfric visited the http://www.uesp.net/wiki/Skyrim:Falkreath_Stormcloak_Camp and was on his way back to Windhelm, with an intermediate stop at http://www.uesp.net/wiki/Skyrim:Rift_Stormcloak_Camp, south of Darkwater Crossing. Why would he take these trips? Well, that's what a military commander is expected to do, not only to make sure the troops are in order, but also to keep their morale high.

So, the Imperials found the details about Ulfric's trip and ambushed him near Pale Pass, through which the player character had just crossed into Skyrim and ofcourse, got ambushed as well.

I was arrested for being too FABULOUS. Sorry, Altmer's personality coming out.

Just another open - ended tutorial. I agree in the immediate scope it looks like you were crossing the Cyro - Skyrim border and got caught out in some sort of skirmish. Then you hear some stuff on darkwater crossing. Its all a bit vague and I think this was deliberate.

Well.. you could be trying to get OUT of Skyrim, like my Bosmer. Or you could be trying to get into Skyrim from Morrowind, like my Nord.

Darkwater crossing is in Eastmarch, which I suppose is near the Skyrim-Morrowind border.

Does your Altmer kill Thalmor?

Not all Altmer are Thalmor so it would make sense.

Also to answer the question it is heavily implied that the Dovahkiin was caught crossing the border by more than just Ralof, even Hadvar essentially mentions it even if you are a Nord. The fact that nobody in Skyrim knows who the hell you are (Which someone in a hold should theoretically know, especially the Jarl since I assume they do a census of sorts and the fact that your character was most likely never a bandit just drives the nail even further) implies it (And if the last Dovahkiin was a bandit at some point which is most likely not the case then at least one bandit camp should recognize them if they were even in one of them). It is literally heavily implied that the Dragonborn was crossing from Cyrodil.

I always kill the Thalmor. Used my High Elf guise to gain their trust.

While it's ultimately up to the player to decide what their character was doing there, I think the reason why we're trying to cross the border from Cyrodiil is because the last game took place in Cyrodiil, so it's like you're moving on to the next game, so to speak.