Google for Java Guid Generator. There will be something cool there. Or start with 1, 2, 3 ... They only have to be unique on one machine and only until the user logs off. BTW: You might want a time-out mechanism so you can periodically purge old sessions or they'll grow forever in memory.
Any chance you will have multiple servers behind a load balancer? Your users might have the IP address of an ArrowPoint or some device like that, and it would divide requests among several real servers. If so, you'll have to find a way to make the user go to the same server after the ArrowPoint makes the first random selection, or a way to copy the session to all servers. Let's hope you can avoid all that!
Oh, XML is fine. I don't introduce XML unless there are some solid benefits. Parsers and DOMs and all that stuff can add complexity; key value pairs work just fine for simple things. Of course if your messages are already XML, then making your "standard header" section fit in is cool.
[ April 10, 2004: Message edited by: Stan James ]