How to pass around collation information

I have been thinking about this collation support business a bit.
Ignoring for the moment where we would get the actual collation routines
from, I wonder how we are going to pass this information around in the
system. Someone declares a collation on a column in a table, and
somehow this information needs to arrive in bttextcmp() and friends.
Also, functions that take in a string and return one (e.g., substring),
need to take in this information and return it back out. How should
this work?

Option 1, make it part of the datum. That way it will pass through the
system just fine, but it would waste a lot of storage and break just
about everything that operates on string types now, as well as
pg_upgrade. So that's probably out.

Option 2, invent some new mechanism that accompanies a datum or a type
whereever it goes. Kind of like typmod, but not really. Then the
collation information would presumably be made available to functions
through the fmgr interface. The binary representation of data values
stays the same.

Option 2a, while we are at it, are there any other things of this nature
that would be worth supporting at the same time? I could imagine that
having the option to pass around the ctype locale or the text search
dictionary in a similar way could be useful. Is this something that
could be combined with typmod or other dormant data type metadata
requirements (PostGIS?, XML?)?

Ideas?