Pdflatex for windows
The following command worked for me, under cygwin. I installed pandoc 1.13.2 and MiKTeX 2.9.5105 64-bit. Then I ran:
pandoc -s \
--latex-engine='C:\Program Files\MiKTeX 2.9\miktex\bin\x64\pdflatex.exe' \
-f markdown_github -t latex \
"my-file.md" -o "my-file.pdf"
The key here is that I gave the full path for MiKText's pdflatex.exe in the --latex-engine key, in quotes, using the windows path (as the pandoc I installed is the windows pandoc, it requires windows-style paths to find resources).
I used -f markdown_github because of the file format of my-file.md
I used -t latext but that's optional AFAIK.
There's no reason to complicate things with Cygwin. Go download and install a TeX distribution for Windows - I personally use TeX Live, but various other distributions are available, such as MikTeX or W32TeX.
If you want to use UTF-8 for your bibliography, and you're using BibTeX, I recommend using bibtexu instead of the regular bibtex (since bibtex doesn't actually support UTF-8). There's a download on the W32TeX site.
If you need to stick with cygwin, install texlive and texlive-collection-latex