This must be done off-chain for standard tokens.
The ERC-721 standard specification -- http://eips.ethereum.org/EIPS/eip-721 -- does not provide an interface to query historical ownership of a token. Other extensions to the standard may include this additional functionality but this will be implemented on a contract-by-contract basis. For example, CryptoKitties (as deployed) will never provide a way to get this information, regardless of what other technologies emerge.
For off-chain applications (dApps, servers) you can find this information by searching the
Transfer event and building your own database of transfers and other log information.
For casual inspection, just look up the token on Etherscan, they have a website where you can find each contract and the tokens on them.