Why didn't he go back to Windhelm where his soliders are? See, after he escaped Helgen, he went back to Windhelm, so why didn't he just head back to Windhelm after Solitude. Cross the border for what? That's the opposite direction of going to Windhelm.

He likes the long walk?

The war had already been going on for a couple of years by the time we get to Helgen. He probably did head straight back to WIndhelm after Solitude.

As for crossing the border, maybe he was trying to recruit allies in Bruma.

iirc if you escape with the legion guy, when you get out of helgan and head to riverwood you can talk to him and he will tell you that the legion set an ambush and waited to capture him.

I don't think he was, I think it was just your character that was and maybe they already had Ulfric, or found him along the way.

This is what I think. Besides I'm pretty sure there is a stormcloak camp near Helgen, and this is where he was probably traveling to.

According to Ralof he was captured at Darkwater Crossing which doesn't appear to be anywhere near the border really.

They were on the way to Darkwater Crossing, that is. Not definite where they were when they were captured.

... to get to the other side.

They were ambushed at Darkwater Crossing, Ralof will tell that when you come with him to riverwood

Do they mention it's Skyrim's border, rather than a hold's border?

He was stapled to the chicken?

The chicken was the one who reported him.

Spoiler Alert:

You were crossing the border with the thief from Rorikstead who will address you directly... something like "You and me, we'd have been alright if not for these guys."

I think it's pretty clear that after being captured and seeing the business end of a chopping block without trial that Ulfric is keeping himself within the confines of his keep somewhat unwillingly... he's laughing and very glad of his freedom when you head into Solitude later, if you take the Stormcloak path.

If they were headed over the border it was to recruit outside of Skyrim... without doing the Stormcloak questline you have only heard half of the story and have been given a really biased view of Ulfric... his plan isn't just one of Nord supremacy, in fact supremacy isn't mentioned. What he wants is Nord control. All the other crap has nothing to do with his plans and he doesn't mention any of it. He is about restoring Nord control of Skyrim and preparing to take on the AD, because that's what will happen when he throws the Empire out of Skyrim.

Thank you everyone, I thought we were caught together because we were on the same ride.

We probably crossed the border, and saw Ulfric. We said hey what's up, can you point me to the college of winterhold, or something like that and did that. You decide to travel with them until you seperate for safety but the Legion comes by. You maintain your innocence but they think you as a spy.

I always assumed I was being executed was because they thought I could be a Stormcloak. WRong place wrong time, I'd assume.

This seems likely, although if that is the case, why didn't he send an adjutant or someone else in his steed? Granted, bravery and all, but really, what would have been the problem with that?

Well, our character is crossing the border INTO Skyrim and not OUT OF Skyrim, right? I also wonder why any of these are wrong? Do we need a Visa, Passport or something?

I think it's because the Imperials do not want anyone entering Skyrim and signing right up with the Stormcloaks. It seems that the Dark Elves were crossing into Skyrim, not the other way around, though the other races may have been fleeing the civil war in Skyrim.

Ulfric was taking the southern route to get to Windhelm to try to evade the Imperials who he knew would surely be chasing him. To further evade them, he then tried to cross over into Cyrodill, but because he didn't have bBorderRegionsEnabled=0 in his Skyrim.ini he had to turn back north...and the rest is history.

Ulfric was pretty much ambushed near Darkwater Crossing so he had no chance to run to Windhelm or call for reinforcements. Tullius for some reason stops in Helgen, my theory is get the execution over before more Stormcloaks attack and free Ulfric, The Dragonborn is basically wrong place at the wrong time and is just along for the ride. Why Ulfric was heading south, could've been heading to Riften, get more weapons for the Stormcloaks, visiting a friend, or Recuriting for the civil war.

^This

the Dragonborn was caught crossing the border, so the Imperials bonked you on the head and threw in the cart. They also caught a horse thief along the way and did the same thing.