TL;DR: cabal install encoding -f-systemencoding
I found a few forum posts on this topic. The most important thing said was
The missing header is langinfo.h - where it originates I don't know, as I don't have it with either Msys/MinGW or Cygwin and my Cygwin is pretty large these days.
From there, I looked on the Cygwin website for where langinfo.h is. Turns out it comes with the default install of Cygwin. And this is its path:
usr/include/langinfo.h
So I installed Cygwin, (actually I already had it installed) and then I ran cabal install like this:
cabal install encoding --extra-include-dirs='C:\cygwin\usr\include'
That registered the package without issue.
Update
Although this does let you register the package, you can't use it. When I tried to GHCi gave me this error:
Loading package encoding-0.6.7.2 ... linking ... ghc: unable to load package `encoding-0.6.7.2'
I am now stuck again.
Update 2
I got some help on IRC from a gentleman named fryguybob. This is another way you can install it: cabal install encoding -f-systemencoding
. That worked for me