Proof of Stake brings new concepts to the Blockchain ecosystem. In the dictionary "Shard" is defined as "A broken piece or fragment, as of pottery or glass".
Shard is a concept not so much related to the Proof-Of-Stake, but rather to the scalability improvement. The idea of 'sharding' is to split the space of possible accounts (contracts are accounts too) into subspaces, for example, based on first digits of their numerical addresses.
Each shard gets its own set of validators (therefore PoS is a pre-requisite), and these validators will not normally need to validate all the shards. Messages (transactions) between the accounts within the same shard would work in the same way as they work today.
Contracts wishing to communicate across multiple shards will need to employ some special techniques, based on the concept of transaction receipts. The crucial difference between calling a contract directly and verifying the receipts is that for direct call one needs to run the code of the contract you're calling, but for verifying a receipt you only need to be sure that receipt cannot be produced by anything else than the transaction you want.
For example, if you want to accept a payment in tokens managed by a different shard, you would generate the payment ID, give it to the payer, ask the payer to pay in the remote shard (with payment ID), and 'bring you back' the receipt.
Sharding allows scaling Ethereum further, because not all nodes of the network will have to execute all of the transactions.
Here is the DEVCON1 talk given by Vitalik Buterin explaining this: https://www.youtube.com/watch?v=-QIt3mKLIYU
In Ethereum, all miners are working on the same problem at the same time. (This is why people usually say: "Equate the Ethereum computer to a Commodore 64". It takes a lot to keep everything in sync.)
My guess is that, with sharding, you could have different segments of miners working on different problems at the same time, and they would somehow check each other to form a global consensus. (This appears hard to me, because what if you're sending ether in a contract running on one shard to a contract running on another shard? Race conditions? I'm sure people smarter than myself are working on this though.)
It seems to me that obvious solution to the scaling problem is fragmentation or specialization. You may call it Sharding, I simply call it inevitable. No different from the evolution of a biological organism if you think about it. I suppose that the question is not so much what is Sharding, but how can it be effectively implemented. In other words, the technical challenge of designing a robust protocol that does not compromise the essence of Ethereum.