Not exactly simple depending on what you want to do with the validation and/or record the submission. I've done this before by expanding the built in JavaScript in the form to encompass my additional box. And I've also written custom JS of my own to create popups with multiple checkboxes, then recorded the responses with the order.
I'm not familiar with your version at the moment, it's a little bit old now and my memory of it is fading. Do you have One Page Checkout? Is it the stock one included with the cart?
Looks like I have a working example of something like you want up on my test site:
http://trainingpen.com/ (this site gets blown away and rebuilt from time to time)
It's based on a particular product being added to cart
http://trainingpen.com/product.php?productid=17611 If you add that to cart and proceed to checkout a special checkbox will appear and it will display the sku.
If you want me to, I can hunt the code down for you and pass it along, though I would need to bill for the time as it will take a bit of work to find as its been a year or more. The solution is probably posted by me right on this forum, but I looked and googled and couldn't find it...