Here's another solution, also from Ubuntu Forums. I think this is somewhat cleaner and more robust: it doesn't involve customizing Ubuntu's locale files (only settings that you're supposed to edit).

Gnome calendar applet adheres to your locale settings. In Ubuntu, you can assign locale components by editing the file /etc/default/locale. Here is what I've got there:

LANG="en_US.UTF-8"
LC_TIME="en_GB.UTF-8"
LC_PAPER="en_GB.UTF-8"
LC_MEASUREMENT="en_GB.UTF-8"

Which means: I want software messages in American, but time, paper size and units in British i.e.weeks starting with Mondays, A4, metric.

Props to artm who posted that!

Of course, LC_TIME="en_GB.UTF-8" is the relevant setting to get weeks to start on Mondays.

You need to log out and back in for the change to take effect.

The best solution for me is to do this on a per-user basis in my own home directory. That way I don't have to edit a system-wide file. (Of course if you want this setting for all of the users on your system you are obviously forced to edit system files.)

What I do is edit the file ~/.xsessionrc to contain the line "export LC_TIME=en_GB.utf8". That's it.

On Ubuntu 12.04 (and later versions I suppose), the easiest way seems to be: System Settings > Language Support, then click on Regional Formats tab and choose from the drop-down list.
In my case I chose "English (Ireland)" which gave me Monday as first day in the calendar, "correct" number formats and currency, and other goodies :)
If you don't find the right option there, you might need to install a language (the other tab of the same window).

The time and date formats in Ubuntu (tried 12.x) are controlled by the locale settings. First you need to find out the current locale being used to control your time and date settings. Open a terminal and enter the following command.

locale | grep LC_TIME

You should see a result that looks something like

LC_TIME=en_US.UTF-8

Change to the locale directory and copy the current locale file to create a new custom file. Adjust the for your locale.

cd /usr/share/i18n/locales
sudo cp en_US en_US_custom

Now edit the new custom file.

sudo gedit en_US_custom

And change

first_weekday 1

to

first_weekday 2

Then make the change in /etc/environment to point to your new custom file.

sudo gedit /etc/environment

Add a line like this to the bottom of the file making sure to adjust it for the custom locale file you want to use.

LC_TIME="en_US_custom.UTF-8"

Source: http://tuxtweaks.com/2008/12/change-the-week-start-day-in-ubuntu/

Based on this page, the settings should go in .pam_environment or .profile https://help.ubuntu.com/community/EnvironmentVariables#A.2BAH4ALw.pam_environment

My default .profile is sourcing .bashrc so I added these lines to my .bashrc since I already have it under source control.

#Change first day of week to Monday
export LC_TIME=en_GB.UTF-8
#Change to metric system
export LC_MEASUREMENT=en_GB.UTF-8

I'm running 14.04.1

UPDATE: 01/15/16 Ubuntu 14.04.03

Having these lines in my .bashrc stopped working earlier this year. Moving the same lines to either .pam_environment or .profile does work. This is a user setting, not system-wide.

For me the advice at https://wired-mind.info/post/528 worked.

Edit the file /usr/share/i18n/locales/en_US

sudo nano /usr/share/i18n/locales/en_US

Find this section:

week 7;19971130;7 

first_weekday   1 

first_workday   2

Set first_weekday to equal 2.

Save and exit the file, then perform:

sudo locale-gen

In my case locale-gen regeneration was important to start to see the change.

For me the easiest way was to update formats in Region & Language Go to Settings->Region & Language and choose your format.

The system will force you to logoff and login to reflect the changes.

This is already a very old topic, I added this answers as reference to future readers looking for the same problem but want a way with less hacking

Use en_DK as locale.

This locale was developed as an official way of writing English in Denmark but it is used outside Denmark, as some sort of generic continental European English locale. It solves the most annoying problems with en_US and does not require any modification of system files. If a more fine tuned solution in desired - the other answers are excellent.

Setting first_weekday in locale

First, determine which time locale is in use. The system wide setting in /etc/default/locale may or may not be overwritten in ~\.pam_environment.

$ cat ~\.pam_environment
…
LC_TIME=en_IE.UTF-8
…

Here, the locale en_IE.UTF-8 appears to be in use. Now, edit the locale source file with administrator privileges. The editor vim is used here, but this can be replaced by, say nano.

$ sudo vim /usr/share/i18n/locales/en_IE

Add the following lines and save the modified locale source file.

first_weekday  2
first_workday  2

Finally, regenerate the locale files with the following command:

$ sudo locale-gen

Log out and in again for this change to take effect.

None of the answers worked for me perfectly. Changing "/etc/default/locale" did not work at all. In settings I did not have my needed format. And after changing ".pam_environment", my "LC_TIME" changed to default "C" locale. I tried "sudo locale-gen", but it did not generate my necessary locale. So I had to force it with command "sudo locale-gen lv_LV.UTF-8". And after restart everything started to work correctly.