How can the BTC Relay contract verify that relayers are providing valid blocks from the Bitcoin blockchain?
The BTC Relay implements an SPV Client on the Ethereum blockchain.
Essentially, the contract keeps track of the longest chain of block headers, under the assumption that it would be difficult to forge a fake chain fast enough to keep up with the real chain. The contract does not validate that each transaction is valid, but does check that the block header itself is valid.
This presents some issues, especially since the provided relay software derives its block headers from http://Blockr.io instead of from a local Bitcoin full node, since if blockr is taken down or starts forging headers, there may not be other validators to compete.