Reading through the source for the decimal module, Decimal.__format__ provides full PEP 3101 support, and all you have to do is select the correct presentation type. In this case, you want the :n type. According PEP 3101 spec, this :n has the following properties:

'n' - Number. This is the same as 'g', except that it uses the current locale setting to insert the appropriate number separator characters.

This is simpler than other answers, and avoids the float precision issue in my original answer (preserved below):

>>> import locale
>>> from decimal import Decimal
>>> 
>>> def f(d):
...     return '{0:n}'.format(d)
... 
>>> 
>>> locale.setlocale(locale.LC_ALL, 'en_us')
'en_us'
>>> print f(Decimal('5000.00'))
5,000.00
>>> print f(Decimal('1234567.000000'))
1,234,567.000000
>>> print f(Decimal('123456700000000.123'))
123,456,700,000,000.123
>>> locale.setlocale(locale.LC_ALL, 'no_no')
'no_no'
>>> print f(Decimal('5000.00'))
5.000,00
>>> print f(Decimal('1234567.000000'))
1.234.567,000000
>>> print f(Decimal('123456700000000.123'))
123.456.700.000.000,123

Original, wrong answer

You can just tell the format string to use as much precision as is included in the decimal itself and use the locale formatter:

def locale_format(d):
    return locale.format('%%0.%df' % (-d.as_tuple().exponent), d, grouping=True)

Note that works if you've got a decimal which corresponds to a real number, but doesn't work correctly if the decimal is NaN or +Inf or something like that. If those are possibilities in your input, you'd need to account for them in the format method.

>>> locale.setlocale(locale.LC_ALL, 'en_US')
'en_US'
>>> locale_format(Decimal('1234567.000000'))
'1,234,567.000000'
>>> locale_format(Decimal('5000.00'))
'5,000.00'
>>> locale.setlocale(locale.LC_ALL, 'no_no')
'no_no'
>>> locale_format(Decimal('1234567.000000'))
'1.234.567,000000'
>>> locale_format(Decimal('5000.00'))
'5.000,00'
>>> locale_format(Decimal('NaN'))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in locale_format
TypeError: bad operand type for unary -: 'str'

For reference (for those that are looking to format numbers similar to how you would format currency), you can use locale.format_string to format numbers

value = 123456789

import locale
locale.setlocale(locale.LC_ALL, 'de_DE') 
print(locale.format_string('%.2f', value, True))

Would return

123.456.789,00