The key with response.sendRedirect is that the browser will make a "brand new request" for the resource you are redirecting to. In that way, you loose all attributes that you set on the 'previous' request.
One option is to use request parameters instead. You could do something like:
String redir = "/foo?a=x&b=y";
response.sendRedirect(redir);
But then your parameters are visible.
The other option was what Bill was mentioning - a page of javascript with a form that submits on page load (with method=post). Then you'd still need to be looking in the request parameter space (not attributes).
As a side note... setting a cookie with response.sendRedirect seems to work, I just tried it the other day and it works.
Tomcat 4.1.29, IE 6, Mozilla.
I suspect that browsers are capable of acting appropriately to both a cookie in the header, and a 300-type "find that page over here" header.