The accepted answer is right, two little side notes.
If you only care about the symlinks you create yourself on the command line, install cygutils-extra package, it includes a winln command, which has the same syntax as ln, but creates native Windows links. Create an alias: alias ln=winln (only works in interactive shell), or even replace the ln file with winln (works in shell scripts as well) - but it might get overwritten the next time coreutils package is updated.
I've only found out it's possible to use native symlinks when I already had Cygwin installed, and added some symlinks by myself as well. So after I set CYGWIN=winsymlinks:native as my system environment variable, I wanted to convert all the existing non-native links to native. Here's what I did.
Just in case, back up your entire Cygwin directory first.
Find all symlinks and save the list to /links file:
cd /; find . -regextype egrep -regex './(dev|proc|mnt|cygdrive)' -prune -o -type l -print >links
Review links.
Create a tar archive with all the links: tar c --files-from=links >links.tar
Extract the tar archive: tar x --files-from=links <links.tar
Since native symlinks are now enabled, tar will overwrite the old Cygwin's symlinks with native symlinks.
Clean up: rm -f links links.tar
P.S. At first I used CYGWIN=winsymlinks:nativestrict, but then I found out that in this mode, ln -s target link fails if target doesn't exist. By contrast, native will create a Cygwin (non-native) symlink link pointing to the nonexistent target - this matches the behavior of ln on UNIX systems. In rare cases, nativestrict can break some programs or scripts, for example Gentoo run-crons script uses a lockfile which is a symlink pointing to the PID of the running process. In nativestrict mode the script stopped working, because it could no longer create the lockfile. Note: run-crons is a crontab helper script on Gentoo Linux, adding support for cron.{hourly,daily,weekly,monthly}/ dirs, it works very well with Cygwin.