Put it on a durable, movable medium
Things that annoy me are
- weak paper stickers glued permanently to hardware
- small labels you don't know where to put
There is no ideal format, really. I'd suggest something similar to a business card - durable paper, in a size for which "containers" (carry boxes, folders, laminating cards) are readily available.
Allow Copy & Paste
Make sure I can copy and paste the key as a whole.
Your input should of course indicate the groups of characters, but when "Paste" only transfers the first group, I am a very unhappy customer.
Barcode
If you stick to print mostly, consider adding a bar code. Depends on your customer base, but it's a worthwhile option if some of them are already expected to have a barcode scanner, and might be expected to enter such a number more than once.
Unfortunately, they are much longer than the numbers, so that might be a format issue. (If you make it to small, scanners won't recognize it, if you make it to big hand scanners can't read it).
For mobile apps e.g. on a phone with camera, you could use image recognition of one of those fancy "square barcodes". (I'd expect libraries for that to be readily available).
Do you insist on print?
Allow the keys to be stored in a (e.g. text) file, give them a specific file extension that is registered for your program.
This way, you can attach a licence to an e-mail, the user just double clicks the attachment, gets a message box
Do you want to install the following licence:
dnord's GreatApp Pro - Evaluation licence (30 days)
[yes] [no]
We use a modified system to (a) have additional data in a licence file, and (b) bundle multiple licences (for separate modules/apps) into one package that can be installed at once.
At least it's an alternate to entering a key for each purchase, welcomed especially by our larger customers.
We never had support calls because of problems receiving or installing the custom file type, though this might be different if you have a consumer product. At least, no support calls because of mistyped keys :-)
General
Have a plan how to deal with "lost licences".
There's no recipe here, I guess with pure software solution you might have to show some lenience to not alienate paying users.
(We usually bind to 19" rackmounted hardware that's hard to lose, so we happily create new licences for a customer as often as he likes).