Daniel Lange's blog

Since version 2.0 the behaviour of grub regarding passwords has changed quite substantially. It can be nicely used to secure the boot process so that a X display manager (gdm, kdm, lightdm, ...) or login prompt cannot be circumvented by editing the Linux kernel boot command line parameters. The documentation is concise but many old how-tos may lead you down the wrong GNU grub "legacy" (the pre-2.0 versions) path.

So this assumes you have a grub installed and working. I.e. if you press Shift during boot, you get a grub menu and can edit menu entries via the e key.

First you need to setup grub users and corresponding passwords:

Run grub-mkpasswd-pbkdf2 to encrypt every password you want to use for grub users (which are technically unrelated to Linux system users at this time).
You'll get a string like 'grub.pbkdf2.sha512.10000...'. It will replace the plain text passwords.

In '/etc/grub/40_custom' add lines like:

# These users can change the config at boot time and run any menuentry:
set superusers="root user1"
password_pbkdf2 root grub.pbkdf2.sha512.10000.aaa...
password_pbkdf2 user1 grub.pbkdf2.sha512.10000.bbb...
# This user can only run specifically designated menuentries (not a superuser):
password_pbkdf2 user2 grub.pbkdf2.sha512.10000.ccc...

Now once you did this grub v. 2.0+ will ask for a supervisor password every time you want to boot any menu item. This is a changed behavior from v. 1.9x which defaulted to allow all entries if no user restriction was specified. So you need to add '--unrestricted' to all 'menuentries' that any user shall be able to boot. You can edit '/boot/grub/grub.cfg' and add --unrestricted to (the default) menuentries. Or you can edit the 'linux_entry ()' function in '/etc/grub/10_linux' so that the 'echo "menuentry ..."' lines include --unrestricted by default:

[...]
echo "menuentry '$(echo "$title" | grub_quote)' --unrestricted ${CLASS} \$menuentry_id_option 'gnulinux-$version-$type-$boot_device_id' {" | sed "s/^/$submenu_indentation/"
else
echo "menuentry '$(echo "$os" | grub_quote)' --unrestricted ${CLASS} \$menuentry_id_option 'gnulinux-simple-$boot_device_id' {" | sed "s/^/$submenu_indentation/"
[...]

Make a backup of this file as it will be overwritten by grub updates. This way all Linux kernels detected by the script will be available to all users without identifying to grub via username / password.

Now issue update-grub to re-generate 'grub.cfg' with the amended menuentries.

If everything worked well, your system can now be booted unrestricted but the grub configuration can only be changed from the grub superusers after identifying with their username and password at the grub prompt.

Bonus point:

If you want to create menuentries that user2 (and any superuser) from the above example user list can run, add blocks like these to the end of '40_custom':

menuentry "Only user2 (or superuser) can run this Windows installation" --users user2 {
set root=(hd1,1)
chainloader +1
}

Update

16.12.2015:
Hector Marco and Ismael Ripoll have found a nearly unbelievable exploit in Grub2 that allows you to tap backspace 28 times to get a rescue shell and that way bypass a password prompt. Time to update!
Read the excellent analysis of the bug and the exploit vector in Hector Marco's blog post.