I've an iPhone 3G running 3.1.2 jailbroken.
I've always used the devteam's jailbreaking tools (quickpwn originally, followed by redsn0w), but geohot's blackra1n was without a doubt the fastest and easiest jailbreak yet. It's very, very simple. Note some people had trouble with the early releases of it (RC1 and RC2) but the latest one currently available on www.blackra1n.com
is very solid. Plug in your phone, open blackra1n and click the button, 15 seconds later you're done.
To ease some fears: Jailbreaking does not damage your phone. In the very worst case scenario, you can just restore to the normal apple firmware. A hassle, but not a big deal. I've never needed to do that, though, and I've jailbroken every firmware since 2.0. Concerned about your warranty? If you need to bring it in for warranty related issues, just restore it first.
So, you run Blackra1n, it'll add a "Blackra1n" app to your springboard. Run that, and install Cydia. Rock is faster, but not as stable. Both install apps from the same places, but Cydia's a little more tried and tested and the maintainer, Jay Freeman (Saurik) is a really great guy who's really on top of maintaining everything. You can have blackra1n install blacksn0w as well if you want to unlock your phone, too, but that's less important.
Speed? Jailbreaking does not slow down your phone, but installing Winterboard does. It's only noticable on a 3G phone. Unfortunately, Winterboard is what you need to install graphical themes. The slowing down is only in opening apps - they take an extra second or two to start up, but there's no difference while actually using them though. To me, this is a worthwhile trade off, but your mileage may vary. Personally, I can't stand the black background, and horrible gray dock thing. It's just so bland and ugly, but to each their own.
As to battery life, simply jailbreaking does not affect it. Apps you install certainly can, though this is always the case. I've found that I get much better battery life while jailbroken than I do otherwise because of the control that SBSettings provides: It's a quick finger swipe to change screen brightness, enable/disable 3G/WiFi/Bluetooth/etc, even inside apps. That alone took my iphone from lasting one day per charge to 3-4 days - I turn off 3G and WiFi when I'm not using them. You can do that with Settings on a virgin phone, but it's a huge hassle and obviously cannot be done inside apps.
Finally, if you have a 3GS phone, it's possible in the future Apple may release firmwares that cannot be jailbroken or unlocked, and on the 3GS you cannot freely downgrade firmwares to older ones (that can be jailbroken, like 3.1.2). If you jailbreak, and run Cydia, it will save your firmware key (phone specific code) so that you can freely downgrade to 3.1.2 in the future should you so decide to. You may not want to unlock your phone now, but the capacity to do so in the future can enormously increase it's selling value later.