Honestly, I wouldn't buy it already Jailbroken. You'll most likely need to sync it to your iTunes no matter what, and maybe even restore it just for good measure. Jailbreaking by your self is not difficult. We are here to help you and guide you along with the Jailbreak process. Let us know when you do get your iPhone 3GS, and we'll be more than glad to help you.
The above address is the newest Jailbreaking application and it is compatible for the latest iOS 5.1.1, and
Absinthe 2.0 supports the following devices on 5.1.1: