How to initialize new disk for UEFI/GPT?

Current util-linux versions of fdisk support GPT, the one I'm looking at here is fdisk from util-linux 2.24.2 (reported via fdisk -v).

Run fdisk /dev/whatever. Have a look at the options with m. Note these change depending on the state of the partition table. First check what state the disk is currently in with p. Note the Disklabel type; if it is gpt you don't have to do anything, you can delete the existing partitions and start creating your own.

If not, use the g option. This will eliminate any existing partitions because fdisk does not convert the MBR table. You can now start adding partitions with n. For the EFI partition, use t to set the type to 1, then the table should read, e.g.,

 Device    Start          End   Size Type
 /dev/sdb1   256    122096640 465.8G EFI System

Obviously that's a bit silly, but hopefully the point is clear. None of your changes take effect until you use w and exit.