From the v2 rules:
How does the Horn of Gondor ability work? The Horn of
Gondor die is placed in another player’s Used Pile in exchange
for a die from their Used Pile. That die goes to your Active
Pool and can be immediately rolled if Horn of Gondor is used
during Phase 2.
So the die you picked does not go to your Used Pile, though unless you use the Horn during Phase 2, you won't be able to use the die you stole this turn.
Burst effects "are in addition to the normal effects of the dice. Burst abilities are optional." So, I would say that the normal ability occurs first, then the additional ability.
However, if you are taking a die the other player wants to move to their Active Pool then it's not much of a "fellowship"! =] We found that with two players after we bought all of the horns we were swapping them around almost every turn. I even used the horn to steal another horn repeatedly until I finally got the "Draw and Roll" effect.