The hard link count is stored in the inode. It starts at 1 when the file is created, increases by 1 each time the link system call is successful, and decreases by 1 each time the unlink system call is successful.
The only way to find all the hard links to the same file, i.e. to find all the pathnames leading to a given inode, is to go through the whole filesystem and compare inode numbers. The inode does not point back to the directory entries.
Directories are a special case: their hard links obey strict rules. (Some unix variants allow root to bypass these rules at the administrator's peril.) The hard links to a directory are its . entry, its children's .. entry, and one entry in its parent directory (the parent being the directory reached by the directory's .. entry).
There is no way to find all the symbolic links pointing to a file. They could be anywhere, including on a filesystem that isn't mounted.
With GNU or FreeBSD find, you can use find /some/dir -samefile /path/to/foo to find all the hard links to the file /path/to/foo that are under /some/dir. With the -L option, you can find all the soft and hard links to that file. You can find an inode by number with the -inum predicate instead of -samefile.