I recently purchased the Iphone 4 from Verizon last Sunday; I have been meaning to jailbreak it since but have been deterred by the apparent inability to restore back to factory should I need to return it for some reason... Thus I am wondering, will I be able to restore the device back to factory following the Jailbreak should the need arise? And if so, which JB software would be recommended?

Save your SHSH using TinyUmbrella and be careful with baseband upgrades and you should be always able to restore to factory.

As far as I know, only greenpois0n (RC6 or higher) can jailbreak the verizon iPhone.

Also be aware that many tweaks from Cydia simply aren't yet compatible with the verzion iPhone as it runs a slightly newer iOS version than the AT&T iPhones.

This will be fixed with the upgrade of both versions to iOS 4.3 due very soon (but SAVE your 4.2.6 SHSH NOW!! it may help you jailbreake 4.3 faster)

Given that I'm a complete noob, could I possibly have a link to a step by step walk through so that I may do this properly?

EDIT: Ok, I just got through acquiring my SHSH with the latest TinyUmbrella; what should be my next course of action? In addition, how do I assure that I retain my Baseband in order to restore should that need arise?

My advice:

Download TinyUmbrella The Firmware Umbrella - TinyUmbrella, unzip/install it
Connect your iPhone to the computer via USB cable
Run TinyUmbrella
Click Save SHSH

Verify that this saves a SHSH for 4.2.6 for your phone
Go to advanced tab, untick "set hosts to Cydia on Exit", click apply
Close TinyUmbrella

---
The above steps are critical to being able to retain the ability to easily jailbreak and also to be able to remove the jailbreak if required in the future
Note that this SHSH is unique to your specific iPhone, so if lose it and get a replacement or if you get it replaced/repaired under warranty - your current SHSH won't work with a replacement phone.

iClarified - iPhone - How to Jailbreak Your iPhone 3GS, iPhone 4 Using Greenpois0n (Windows)

what if I didn't untick "set hosts to Cydia on Exit"?

Then sometime in the future you will probably get an error if you restore your iPhone to the same or newer iOS version.
Right now, you need to use greenpois0n to get past this error (eventually, there will be an option built into TinyUmbrella to get past this error without actually re-jailbreaking)

Oh, I haven't JBed yet, I'm just prepping everything for when I do Jailbreak...

Also, I went ahead and unticked the box in question following a re-acquiring of the SHSH, will that cause problems in the future?

In addition, can't I just restore from TU itself instead of going through iTunes?

It's good to be prepared and have researched this well before you start!

No it should not cause problems in the future, it's easy to turn it on again if necessary.
There are advantages to having this on and advantages to turning it off. Right now on the iPhone 4 only, I would recommend turning it off if you don't rely on unlock via ultrasn0w.

No you can't restore via TU instead of iTunes

Detailed explanation of why this isn't currently possible:
TinyUmbrella only saves the SHSH blobs (these are used to personalise the IPSW that iTunes uses to restore your iPhone - without this personalisation, your iPhone will reject the contents of the IPSW as not valid)

The author of tinyUmbrella is working on a program that can also perform the restore function that iTunes currently performs. There is also another (linux only) program that can restore the phone - but it's not really ready for general use yet.

So if I'm not mistaking, all I need now is the IPSW file for iOS 4.2.6, correct?
In addition, by being able to restore at a later date, I eliminate all trace of having JBed my phone; thus being able to slide by a voided warranty, correct?

Oh, almost forgot, what about the Baseband? Do I have to worry about that at all? Is my ability to restore going to be impeded if I just do a straight JB with Green Poison?

You can find the IPSW here http://www.hackint0sh.org/f127/22056.htm

As we have answered 100s of times now (ie use the search function)
A restore of the OS, then activating legitimately via iTunes and setting the phone up as new will remove ALL traces of jailbreak.
These are also the same steps that Apple recommended as part of their troubleshooting procedure (they recommend of course restoring the latest iOS version) before you take a device in for service.

There is only one baseband version (for now) for the Verizon iPhone. I'm not sure if blocking baseband upgrade will ever be so important for the CDMA iPhone as a non-official unlock is a lot more complicated (and requires steps which are illegal in the US) than the GSM iPhone unlock.