Central cancer registries are often used to survey population-based samples of cancer survivors. These surveys are typically administered via paper or telephone. In most populations, web surveys obtain much lower response rates than paper surveys. This study assessed the feasibility of web surveys for collecting patient-reported outcomes via a central cancer registry. Potential participants were sampled from Utah Cancer Registry records. Sample members were randomly assigned to receive a web or paper survey, and then randomized to either receive or not receive an informative brochure describing the cancer registry. We calculated adjusted risk ratios with 95% confidence intervals to compare response likelihood and the demographic profile of respondents across study arms. The web survey response rate (43.2%) was lower than the paper survey (50.4%), but this difference was not statistically significant (adjusted risk ratio = 0.88, 95% confidence interval = 0.72, 1.07). The brochure also did not significantly influence the proportion responding (adjusted risk ratio = 1.03, 95% confidence interval = 0.85, 1.25). There were few differences in the demographic profiles of respondents across the survey modes. Older age increased likelihood of response to a paper questionnaire but not a web questionnaire. Web surveys of cancer survivors are feasible without significantly influencing response rates, but providing a paper response option may be advisable particularly when surveying older individuals. Further examination of the varying effects of brochure enclosures across different survey modes is warranted.