I give encounter XP, and in-character XP, but rarely story XP. I don't have a story beyond that which the players end up making for themselves. I don't have a plot figured out ahead of time, so I'm not able to hand out breadcrumbs when they follow it.
On the other hand, when a player has their character do something strikingly in-character (or clever), they get a little bonus - usually 10xp per character level. I bump it up to 20 per character level for truly incredible in-character behavior. I just handed out the first XP for my new campaign. This is the XP I handed out:
The cleric of the God of Mercy:
Attemting to assist dying man in ally and taking his body to the guards: 10xp
Investigating the ship (Detect spells, talking to sailers): 10xp
Binding the wounds of a dying enemy: 20xp
Participating in the Cultist fight: 150xp
Total: 190xp
The ranger/trapper dudette:
Attempting to track the dead man back to his starting point: 10xp
Suggesting staking out the ship: 10xp
Tailing the sailers into town: 10xp
Participating in the Cultist fight: 150xp
Total: 180xp
The Sorceress/Barmaid Dudette:
Gathering Information: 10xp
Charming the Dockmaster: 10xp
Tailing the cultist: 10xp
Participating in the Cultist Fight: 150xp
Total: 180xp
By increasing the number of XP gained for the bonus activities as the characters increase in level, I'm actively encouraging them to act in-character in such a way that it will still mean something at 8th or 17th level. This was their first little adventure, so I'm hoping to wean them off of the more mundane bonus-XP items (gathering information, for instance) and get some real role-playing stuff going on (with the plot they're coming up with, it shouldn't be hard).
Without bonus XP, it's hard for a character to justify doing things in-character that could potentially be bad strategic ideas (binding the enemy's wounds, for instance). I don't want the characters to behave like they're in some sort of game; I want them to behave like actual people.