Upgrading ethernet network to gigabit?

We're getting new computers with gigabit capability and a new switch for the
office.

Is replacement of all cabling and receptacles required in order to achieve
gigabit speeds? I've been asked this question, and would like to have some
idea of what's achievable.

What speeds can we likely achieve with A) no wiring upgrade, B) upgrading
patch cables only (from computer to receptacle), C) upgrading patch cables
and RJ-45 receptacles?

I realize that, with any accuracy, this is not an answerable question, but
some likely ball park figures based on your experience would be appreciated.

Thanks,
--
Al, the usual

.