This answer is probably 9 years too late, but I feel that the above answers don't adequately answer the question.
The definition of 32-bit and 64-bit are not well defined or regulated by any standards body. They are merely intuitive concepts. The 32-bit or 64-bit CPU generally refers to the native word size of the CPU's instruction set architecture (ISA). So what is an ISA and what is a word size?
ISA and word size
ISA is the machine instructions / assembly mnemonics used by the CPU. They are the lowest level of a software which directly tell what the hardware to do. Example:
ADD r2,r1,r3 # add instruction in ARM architecture to do r2 = r1 + r3
# r1, r2, r3 refer to values stored in register r1, r2, r3
# using ARM since Intel isn't the best when learning about ISA
The old definition of word size would be the number of bits the CPU can compute in one instruction cycle. In modern context the word size is the default size of the registers or size of the registers the basic instruction acts upon (I know I kept a lot of ambiguity in this definition, but it's an intuitive concept across multiple architectures which don't completely match with each other). Example:
ADD16 r2,r1,r3 # perform addition half-word wise (assuming 32 bit word size)
ADD r2,r1,r3 # default add instruction works in terms of the word size
Example bit-ness of a Pentium Pro CPU with PAE
First, various word sizes in general purpose instrucion:
- Arithmetic, logical instructions: 32 bit (Note that this violates old concept of word size since multiply and divide takes more than one cycle)
- Branch, jump instructions: 32 bit for indirect addressing, 16-bit for immediate (Again Intel isn't a great example because of CISC ISA and there is enough complexity here)
- Move, load, store: 32 bit for indirect, 16 bit for immediate (These instructions may take several cycles, so old definition of word size does not hold)
Second, bus and memory access sizes in hardware architecture:
- Logical address size before virtual address translation: 32 bit
- Virtual address size: 64-bit
- Physical address size post translation: 36 bit (system bus address bus)
- System bus data bus size: 256 bit
So from all the above sizes, most people intuitively called this a 32-bit CPU (despite no clear consensus on ALU word size and address bit size).
Interesting point to note here is that in olden days (70s and 80s) there were CPU architectures whose ALU word size was very different from it's memory access size. Also note that we haven't even dealt with the quirks in non-general purpose instructions.
Note on Intel x86_64
Contrary to popular belief, x86_64 is not a 64-bit architecture in the truest sense of the word. It is a 32 bit architecture which supports extension instructions which can do 64 bit operations. It also supports a 64-bit logical address size. Intel themselves call this ISA IA32e (IA32 extended, with IA32 being their 32-bit ISA).
References
ARM instruction examples
Intel addressing modes