The Web bears the potential to become the world's most comprehensive knowledge base. Organizing information from the Web into entity-relationship graph structures could be a first step towards unleashing this potential. In a second step, the inherent semantics of such structures would have to be exploited by expressive search techniques that go beyond today's keyword search paradigm. This work proposes a wide variety of novel search and ranking strategies over data that is organized in entity-relationship graphs. All presented techniques have been implemented as components of the NAGA search engine and published in renowned international conferences. NAGA itself is a fully implemented prototype system and is part of the YAGO-NAGA project.