Can the Bitcoin network be used as a timestamping service? Does the Bitcoin protocol provide means to add some freely definable data to transactions such that a small transaction could actually be used to timestamp arbitrary data?
Yes, the bitcoin network can be used as a timestamping service

Here is an article about it
https://www.strongcoin.com/en/blog/using_the_blockchain_as_a_trusted_timestamping_service

Here are additional instructions:
https://bitcointalk.org/index.php?topic=52715.0