This is my usual workflow when jailbreaking my device:
1) Using iTunes, back up iDevice.
2) Using iTunes, do a full restore. This completely wipes the device and gives it a fresh install of iOS. If iPhone 4S, do a full restore to 6.1.1. If any other device, do a full restore to 6.1. You can download the iOS update files from the web. They are called IPSW files as that is their extension. If you download the IPSW you can tell iTunes to use it to restore your device by holding down Shift when clicking on Restore (on Windows, I think it's Option on a Mac).
3) When the restore is done, set up device as New and go through the setup prompts on the device. Feel free to just skip through them (your previous settings are in your backup after all). Activate via cellular if that's necessary.
4) After that, jailbreak. Normally right after the jailbreak is done I open Cydia to let it do its initial setup. The device then reboots. After that,
5) Restore your settings from your backup in iTunes.
6) After that your device is back to where it was when it began, but now it has Cydia. You can now use Cydia to browse jailbreak tweaks.