Most state health departments (SHDs) have adopted and are using Facebook and/or Twitter. Among the friends and followers of SHD Facebook and Twitter pages are other SHDs. These connections form networks with the potential to facilitate dissemination of evidence around effective public health practice among health departments nationwide. To better understand the composition and structure of these networks, Facebook and Twitter connections between SHDs were collected and examined. More SHDs were connected to each other on Twitter (n = 37) than on Facebook (n = 24). The Twitter network was denser (dTwitter = 0.06; dFacebook = 0.01) with more clustering (CTwitter = 0.06; CFacebook = 0.01). Larger health departments were more central in the Facebook network, whereas health departments with a longer social media presence were central on Twitter. Health departments on Twitter were also more likely to be following other health departments in the same geographic region, whereas the same was not true on Facebook. California and Florida were central in the Facebook network, whereas Minnesota, Missouri, Louisiana, and Rhode Island were central on Twitter. Overall, the Twitter network demonstrated greater potential to disseminate information quickly to a larger group of SHDs. More information is needed on the feasibility and effectiveness of using Web 2.0 for dissemination and other public health activities.