The spec says that only ASCII characters are allowed in HTTP headers. Anything else can be ignored and therefore won't work. If you need to store non-ASCII data then encoding is the only way. I don't believe that URL encoding is the correct solution though. URL encoding is used to map characters that have special meaning in a URL (like slash, question marks and ampersands) to something else so the URL can be properly encoded. That isn't an issue for HTTP headers as they are just string values. You can put anything you want in them (as far as ASCII goes).
The correct solution, to me, is to Base64 encode whatever value you have. This will convert the entire string to a series of hexadecimal values that you can then decode on the other side. This is the primary approach we use to encode things like binary data that needs to be stored as a string. In C# it is easy to do.
var someStringToEncode = "ABC123";
string encodedString = Convert.ToBase64String(Encoding.Unicode.GetBytes(someStringToEncode));
//To decode
string decodedString = Encoding.Unicode.GetString(Convert.FromBase64String(data));
Note that I'm using the Unicode encoding here because it doesn't matter for base64 encoding. But each side of the fence needs to use the same encoding to avoid translation issues.