"Can we each have separate Icloud IDs and still have one Apple ID we use for Itunes account?"
Yes, that's the suggested way of doing it.
As for starting from scratch - you need to decide which Apple ID to use for the mac. If each member of the family uses the mac, then set up a seperate account for each and use the Apple ID (the one used for iCloud) to sign into icloud. Use the common ID for itunes purchases. I'd suggest first syncing devices to icloud to get whatever data is important (contacts, events, ...) saved. When on the mac you connect to an iCloud account, the data (just synced from a device) will come down to the mac (for that account).
Tell us what "data" you want to get to the new Mac?
Most important info on Iphones and Itouches are contacts, calendars, PHOTOS, and reminders?
I will set up my Iphone for Icloud and save those items above to it. So my iphone will be the first device I will try this with.
Then should I hook up my phone to Itunes and will it erase everything on my phone?
How do I used Itunes to put the contacts, calendar, etc back on my phone?