Sorry about the delay answering, I've been on the road in California for the past week.
mtnclimber is right that the NYSGIS trail data is one of the data sources. I also used a large set of shapefiles for the New York state parks that I got from Andy Arthur (who got them on a Freedom of Information request from the NYS Office of Parks, Recreation and Historic Preservation). I've been trying to integrate what few trails are on Open Street Map, as well as some corrections of my own (fixing the misalignment between Balsam and Haynes, for instance).
The water features are from NHD and the USFWS wetlands inventory. The topography is from NED. Roads, railroads, airports, towns, and landmarks are Open Street Map. The public land boundaries are from NYSGIS. The lean-to's, trail registers, fishing sites, boat launches, and so on are from another file that Andy got from DEC under Freedom of Information. (The parking lot locations in that file are all messed up, by the way.) I'm sure there are more data sources that I'm forgetting, I'd have to look at my programming to see what else I've put in there.
There are indeed software packages for getting this stuff into a GPS-equipped phone. The one I've been using is called
MOBAC (MOBile Atlas Creator) --
http://mobac.sourceforge.net/. It can interface with quite a variety of map packages on the phone: the one I've been using is Backcountry Navigator, and so far it's been reasonably satisfactory.
I'm surely not trying to compete with NYNJTC here, but at this point I can't use their maps, because they're only for Apple. I'll probably buy some of them when they come out for Android, but right now this map is about the best I can do. As others have observed, the USGS maps don't have most of the trails. I did this project mostly for my own use, but I'm always willing to share.
Obviously, I have no official data sources for the unofficial trails. But if people have data, I'll be happy to look into including it. Probably the easiest way would be for people to get their trail data into Open Street Map, and let me pull it from upstream. (Actually, in a few places, like Bear Mountain/Harriman, I do have some of the unofficial trails; apparently, whoever put the files together there saw fit to include some of the old woods roads and unmarked trails.)
If this winds up going anywhere and I can clear the legal issues, I'll try to look into making it available for wider download. Right now, my available bandwidth won't take it. My current working map covers New York State south of the Mohawk and east of Binghamton (with the exception of eastern Long Island), and it's about 6 gigabytes. This stuff always gets into slinging an ungodly amount of data.