Conversational interfaces that allow for intuitive and comprehensive access to digitally stored information remain an ambitious goal. In this thesis, we lay foundations for designing conversational search systems by analyzing the requirements and proposing concrete solutions for automating some of the basic components and tasks that such systems should support. We describe several interdependent studies that were conducted to analyse the design requirements for more advanced conversational search systems able to support complex human-like dialogue interactions and provide access to vast knowledge repositories. In the first two research chapters, we focus on analyzing the structures common to information-seeking dialogues by capturing recurrent patterns in terms of both domain-independent functional relations between utterances as well as domain-specific implicit semantic relations from shared background knowledge. Our results show that question answering is one of the key components required for efficient information access but it is not the only type of dialogue interactions that a conversational search system should support. In the third research chapter, we propose a novel approach for complex question answering from a knowledge graph that surpasses the current state-of-the-art results in terms of both efficacy and efficiency. In the last research chapter, we turn our attention towards an alternative interaction mode, which we termed conversational browsing, in which, unlike question answering, the conversational system plays a more pro-active role in the course of a dialogue interaction. We show that this approach helps users to discover relevant items that are difficult to retrieve using only question answering due to the vocabulary mismatch problem.