Another way to look at it is if the states are within a small distance of each other. Using PostGIS, you can do this rather easily:
SELECT
s1.name state1,
s2.name state2,
ST_DWithin(s1.the_geom::geography,s2.the_geom::geography,500) share_border
FROM state_polygons s1, state_polygons s2
WHERE s1.name != s2.name AND s1.name < s2.name
ORDER BY share_border DESC, state1 ASC, state2 ASC
I have a data table of states in my CartoDB account and ran that query. Depending on the data, you can choose a more accurate number than 500 meters as I did here. I pulled the state polygons from CartoDB's data library. The state polygons were originally from Natural Earth Data.
This produces a data table like this: