Primary or logical partition

Lưu Vĩnh Phúc's answer is basically correct for disks partitioned with the older MBR scheme, although I personally would recommend minimizing the use of primary partitions, since this will give you greater flexibility should you later need primary partitions for some other purpose.

Most new computers, though, use EFI/UEFI firmware, which generally uses the newer GUID Partition Table (GPT) partitioning system. Under GPT, there's no such thing as primary, extended, or logical partitions; GPT has one partition type (which some tools report as "primary" partitions, although that term is meaningless in the absence of the other types). GPT supports up to 128 partitions by default, although that value can be raised with the right software, if necessary.

If you're using a computer that was sold in the last two years, you probably have the option of booting it in EFI mode or in the older BIOS (aka CSM or legacy) mode. If you're dual-booting Linux with Windows, you should be sure to install Linux in the same mode that Windows uses. Computers that ship with Windows 8 almost invariably use EFI-mode booting, so if that's your situation, you should plan to use EFI-mode booting and GPT. If you're dual-booting an older computer, it probably uses BIOS-mode booting by default, although you'll need to check your computer to be sure. If you're setting up a Linux-only computer, you have your choice. Note also that Linux can use GPT even on a BIOS-based computer, although there are caveats with some BIOSes. Also, Windows requires MBR partitioning when booting in BIOS mode, so if you're dual-booting with Windows in BIOS mode, you must use MBR.

To sum up:

• BIOS-mode dual boot with Windows: Use MBR
• BIOS-mode Linux-only setup: Use MBR or GPT, as you see fit (but MBR is the safer and more traditional choice)
• EFI-mode Linux-only setup: Use GPT
• EFI-mode dual boot with Windows: Use GPT

MBR only allows a maximum number of four partitions. Hence you must create at least one extended partition for the logical partitions. In general the extended partition should be placed at the end of the drive.

The real partitioning scheme depends on you. You can create only /boot as primary, or /boot and / (root) as primary, and the rest as logical.

Previous versions of Windows require the system partition to be primary, otherwise it won't boot. Windows Vista and later versions could be installed to a logical partition without problem, but a primary system partition may still be recommended. So in general creating the first three partitions as primary and the rest as logical is recommended. You may reserve one of the primary ones for Windows and let Linux use the rest.