We present the first comprehensive search for submillimeter and radio emission from the host galaxies of twenty well-localized \gamma -ray bursts ( GRBs ) . With the exception of a single source , all observations were undertaken months to years after the GRB explosions to ensure negligible contamination from the afterglows . We detect the host galaxy of GRB 000418 in both the sub-mm and radio , and the host galaxy of GRB 000210 only in the sub-mm . These observations , in conjunction with the previous detections of the host galaxies of GRB 980703 and GRB 010222 , indicate that about 20 \% of GRB host galaxies are ultra-luminous ( L > 10 ^ { 12 } L _ { \odot } ) and have star formation rates of about 500 M _ { \odot } yr ^ { -1 } . As an ensemble , the non-detected hosts have a star formation rate of about 100 M _ { \odot } yr ^ { -1 } ( 5 \sigma ) based on their radio emission . The detected and ensemble star formation rates exceed the optically-determined values by an order of magnitude , indicating significant dust obscuration . In the same vein , the ratio of bolometric dust luminosity to UV luminosity for the hosts detected in the sub-mm and radio ranges from \sim 20 - 800 , and follows the known trend of increasing obscuration with increasing bolometric luminosity . We also show that , both as a sample and individually , the GRB host galaxies have bluer R - K colors as compared with galaxies selected in the sub-mm in the same redshift range . This possibly indicates that the stellar populations in the GRB hosts are on average younger , supporting the massive stellar progenitor scenario for GRBs , but it is also possible that GRB hosts are on average less dusty . Beyond the specific results presented in this paper , the sub-mm and radio observations serve as an observational proof-of-concept in anticipation of the upcoming launch of the SWIFT GRB mission and SIRTF . These new facilities will possibly bring GRB host galaxies into the forefront of star formation studies .