All transactions that have occurred since the creation of Bitcoin are stored in the block chain. A copy of the block chain gets downloaded automatically to your system once you start your Bitcoin client. Currently, 149520 blocks have been created, so it may take a while to download all of them.
It is expected that future versions of Bitcoin will address this issue, so that Bitcoin scales better, even for low memory, low storage devices.
That's one block for every 10 minutes since Bitcoin started right? That would make sense, it implies about 2.85 years worth of blocks.
Is each block in the chain the same size and overheard, or does that increase with the number of transactions that happened in that block? I can see that becoming a major hassle given that blocks in the chain never retire. If it becomes a problem, I would consider chipping in for a bounty for a solution.