I have a tri-sports cabinet that I did the same thing to, it's actually a WIP in my garage right now. I haven't stained it yet, but I found the adhesive was extremely tough to get off. Heating it and scraping with a putty knife did nothing, and no chemical would take it off. I ended up taking the cabinet outside and used a palm sander with 60 grit paper to take the adhesive off. I then used 100 grit paper to smooth it out a little, and then 150 to finish the sanding. I haven't begun to stain it yet, but mines down to the point where it feels like real wood.
Also, you may notice as I did that some of the graphics may seem stained into the wood itself, and that sanding will help, but it won't make it disappear. For mine I can only speculate that this machine was in the sun a little (would make sense, the black paint is actually a little brownish / looks washed out) and faded the cabinet some.
Good luck!