As many as 20% of English speakers have dyslexia, a language disability that impacts reading and spelling. Web search is an important modern literacy skill, yet the accessibility of this language-centric endeavor to people with dyslexia is largely unexplored. We interviewed ten adults with dyslexia and conducted an online survey with 81 dyslexic and 80 non-dyslexic adults, in which participants described challenges they face in various stages of web search (query formulation, search result triage, and information extraction). We also report the findings of an online study in which 174 adults with dyslexia and 172 without dyslexia rated the readability and relevance of sets of search query results. Our findings demonstrate differences in behaviors and preferences between dyslexic and non-dyslexic searchers, and indicate that factoring readability into search engine rankings and/or interfaces may benefit both dyslexic and non-dyslexic users.