"Montana" was released as the single for the album. Rather than a standard 7" or 12" vinyl record, the disc was green and die-cut into the shape of the 48 contiguous states. It was pressed by Erika Records. The single also featured the non-album track "Louisiana" as the B-side. Originally, "South Carolina" was the album's single, but the track was too long for the grooves to fit in the small area between the labels and the edges of the United States. The labels were marked with no text, instead only showing silhouettes of their respective states.
State Songs originally existed as a short EP that John Linnell released through the Hello Recording Club. The album is notable for its use of the carousel organ, featured in four tracks. Linnell has stated that the organ was used to add variety among the standard human musicians. Two different band organs are featured on the album. The paper rolls for the organ were cut by Bob Stuhmer and adjusted by Linnell.
State Songs received positive reviews from critics. Matthew Springer, writing for Allmusic, praised the album's surrealism and eclecticism. Music critic Robert Christgau cited "The Songs of the 50 States" and "New Hampshire" as highlights from the album.
The album spent four weeks on the CMJ 200 chart, peaking at #18.