The basic concept behind Bitcoin currency is distributed consensus. Being a P2P protocol, each and every node is required to obtain a full and global knowledge of every account's (wallet) status.
The differences with PayPal are easy to explain: in a client-server model, like your contractual relationship with your regular bank, the bank holds the huge database of all accounts of their customers, plus the transaction history with other banks. You, as a client, act as a thin client with knowledge limited to only your account. When you arequest a cashier an extract of your accoun't activities, or log in to your internet banking, a view on a database is triggered to obtain only your data.
In Bitcoin, that's completely different: there is no central data warehouse and the security principle is that nobody fully trusts nobody unless a message is signed with corresponding private key. So, what else better storage rather than all network nodes?
In both cases, the database still exists, but is located differently. Central VS distributed.
Let me finish with a short answer, that may be the repetition of previous answers: In Bitcoin, when you receive a payment, you have to validate that the sender account has enough money for the transaction to be valid (anyone could send an uncovered check else). The only 100% sure way is to check the transaction history for the sender to see if he really received the money he's sending to you from someone or from mining.