How to replace some substrings with consequitve numbers in a string using regular expression in java?

How to replace some substrings with consequitve numbers in a string using
regular expression in java?

I have the following text:
some cool color #12eedd more cool colors #4567aa
I want that this string will be transformed to:
some cool stuff #{1} more cool stuff #{2}
How is it possible to do it in Java (1.6)?