UEFI (Unified Extensible Firmware Interface) is a modernized replacement to BIOS (Basic Input/Output System). The specification is maintained by the collaborative non-profit UEFI Forum. UEFI is supported by both recent versions of both Linux and Windows. UEFI firmware with legacy BIOS support has started appearing on Sandybrige (220,420,520,etc.) Thinkpads. On supported machines, the firmware configuration utility (Thinkvantage->F1 on machine starup) has the option of enabling one or both UEFI/BIOS as well as providing the option to specify the order with which the machine tries to boot.
Though the specification has been around since the late '90s, UEFI only recently started appearing on commodity hardware. Macs are a slight exception, though they do not strictly adhere to the UEFI standard.
Linux can boot as usual in BIOS mode, however the ELILO boot loader or recent versions of Grub 2 are necessary to boot in UEFI mode. Grub 2 support for UEFI is still in its infancy however and mixed success has been had booting in pure UEFI mode.