You get yourself into some pickles. I had a look at some back posts and seems that you use ubuntu but I'm not sure which version.
As said before kxstitch is a KDE package, but no reason why it will not work in Gnome.
From what I can see there is a package for ubuntu 10.x but I think not for ubuntu 11.x, maybe somebody can check the repo. This comes from the equivalent linuxmint versions which are based on Ubuntu.
Some screenshots of a LM10kde with a vile theme.
http://i.imgur.com/Ao6ey.jpgfirst one, it installs but there are some errors regarding menu. However it did show up as expected in the graphics menu. If not maybe it is a gnome thing as GnuTux mentioned.
second one, if you want to know where files are installed you can usually fire up synaptic package manager, right click on an installed package, choose properties, then installed files.
Not shown but also in synaptic you can see the installation history which shows what other packages had to be installed.
third one, if you need to run from a terminal to see if there any error messages, it is as easy as that. In this case kxstitch - worth noting that sometimes for old or ancient stuff or bash files or... you might have to use (dotslash) ./kxstitch to start an executable file.