I've ran into this problem recently too. Sometimes forcing users to accept cookies is not an option. You might want to skip on cookies alltogether, or use both (cookies and query_string options). I chose for the last (for I hate links/URIs that contain session IDs).

First I see wheter the user accepts cookies or not. The basic idea of how to do that can be found at merlyn's WebTechniques pages.

If the user does not accept cookies, you store that information in the session (no_cookies = true, or -might be nicer-, cookies = false). That way, you can tell your template to throw in the session id. It's a hellish task to change all URLs this way, but at least Template Toolkit gives you the power to add macros. I've used something like this:

[% MACRO gen_link BLOCK %]
<a href="/[% m %]/[% p | uri | html %][% IF no_cookies %]/[% sid %][% 
+END %]">[% t %]</a>
[% END %]
[download]

(I use CGI::Application and have a little URI Parser set up to strip the session id from the path info)

Then I call that macro like this

# m = CGI::Application "module"
# p = the "page" in question
# t = the linked "text"

[% gen_link(m="shop", p="band/$item.bandname", t="$item.bandname") %]
[download]

There are probably better ways to tackle all of this (you might be interested in Template::Plugin::URL), but at least it "works" for me ;)