USokoban is an excellent sokoban implementation by Yang Chao.
I have put it on github and added a makefile, edited slightly to my preference (no need to 'install' it).
type make
On first run use ./usokoban and it will set the current working directory as an absolute path in the preferences file ~/.usokoban. After that you can run usokoban from any directory.
I collected some level sets which you can easily find by searching on the internet.