Buy a rubber date stamp. Easiest, most consistent and most permanent without affecting your prints (running the page through the printer again is a bad idea, just as printing on the wrong side of the paper is a bad idea). Writing by pen could end up marking the other side with an embossed mark. Writing in marker might not get you the consistent look you want.

Otherwise, what you're looking for isn't so much a piece of software, but a special feature of a printer. Printing on the bac side at the lab is a feature of the machines they use to produce the photos. I bet some places do this for digital as well. If youre intending to print a lot of pictures (especially small sizes like 4x6) then it's not cost effective to do it yourself. Get them done at Costco or Wallmart or your friendly neighborhood lab. Here (in the Toronto area) I think the price is now down to the same cost per print as film (perhaps even lower).

Bruno