I have worked remotely for just about 1 year right now. This answer may not please you, but I became remote by starting on-site for the company I now work remotely for.

After about 2 years of working in the office I told my manager that I would be moving to another state and that I was interviewing for remote positions. I also said I would stop interviewing if they gave me the ability to work remotely, which they did (and I was very, very happy to stay). It is going to be difficult to find your first remote job, but this is how I did it.