After doing RSpec for a while, writing with Test::Unit seemed really clunky and annoying, especially when reading tests.
I don't use the new Story stuff in RSpec. That seems geared more toward non-programmers who spec things out to be coded by others.
Writing tests is like writing anything else: you can write shitty tests in Test::Unit or RSpec. Neither one will necessarily help you to write good, short, idempotent tests, which is the really important part.
My advice is to watch a few Peepcode screencasts (I gotta start collecting affiliate fees from that guy, I drop his name so much) and just pick a method and start. Don't get too obsessed with exactly which flavor of the testing religion you are adopting; play around with it a while. RSpec is as good a place to start as any, although you should obviously know enough about Test::Unit to read and recognize other people's vanilla unit tests.
I'd be sure to try autotest with whatever else you use, though, because it's fun to get the dynamic feedback.
You can learn way, way too much about Rails testing by reading Jay Fields' blog. There was also some useful stuff on the Thoughtbot blog, back when I was actually paying attention.