Appropriate character encoding / collation to store URLs?

It doesn't really matter as far as I can see. The characters valid in a URL are represented in any character set I know of, and I wouldn't use different collations between tables and columns - you'll get "illegal mix of collations" problems on any attempt to join them or perform any other kind of cross-column or cross-table operation (see my recent problem here).

Correct me if I'm wrong of course.