I will answer in the order of the questions asked:
- Who, if anyone, should I attempt to sell my TeX skills to?
Consulting skills to people who have little background in LaTeX and typesetting. People who want to outsource typesetting and want it done nicely. Universities are a good environment for LaTeX because they have a large output in publications but most of the editors don't have any tranining doing so. Being able to get LaTeX-quality typesetting can increase the quality of their output and make them stand out from peers.
Would, say, a publishing company be interested? Or do they generally
seek people with a much stronger background in TeX & friends than
I think going directly for a publishing company might be rather difficult if you don't have any previous experience or credentials. Also, a publishing house usually has a pretty fixed way of doing things. If they use LaTeX already they probably already have their staff. If they don't, they might not care to try. I would suggest offering to work for free for, say, university staff, so you collect credentials and gain experience working with a real publisher. Once you have done that, you will probably have some contacts and a better understanding of your environment (is there a demand for the service I want to provide, etc).
If you are directly getting paid on account of your TeX skills, how
did you get started?
I sometimes do paid work using LaTeX. But I also sometimes us it as part of my job which is mainly other work related to XML data. LaTeX is interesting for automatically creating PDF output from XML data, for example. It also is very useful for special typesetting needs in the Humanities.
To get started, I just began telling people I like LaTeX and showing my work. When people needed help, I helped. And now, once they actually have some money for typesetting services, they ask me.
It's probably not a way to make lots of money and get started quickly, but there isn't an extreme demand for LaTeX typesetting (I think). So it makes sense to slowly build a potential "customer base".
Place yourself in an environment where there is a considerable need for typesetting and publishing, then advertise what you can offer. You won't get lots of jobs at first, but you can get some if you are patient.
I wrote a lengthy article on my blog on "Earning money with LaTeX". There I give a lot of additional information, including what I would advise you do, what skills I think you should have to get started and also some interviews with people from the TeXLaTeX community who actually make a living from LaTeX and kindly told me of their experiences.