From your server:
Code:
ssh -V
whereis sshd
ls /etc/init.d | grep sshd_not_to_be_run
The first will tell you the whether ssh is installed, together with the version. The second will tell you whether sshd is installed, the third whether it is set to run at boot time or otherwise (the absence of the file indicates that it will be started via /etc/init.d).
Assuming that you have sshd running, then try to connect using the verbose switch (from another machine)
EDIT: the package ssh includes both the client and server, thus if you have ssh installed you almost certainly also have sshd.
Cheers,
mj