Increasing functionality, growing media volumes and dynamic data in today's in-vehicle information systems bear new challenges for user interaction design. Traditional hierarchical and menu-based interaction can only provide limited support while new search-based approaches are promising. In this work we assess different search techniques and search-based user interfaces. In particular we compare free search across all data items with categorized search. Our experiments with functional prototypes show that free search is more efficient and easier to use than searching within categories. Tests in a driving simulator show promising results regarding safety and workload. Means for alphanumeric input appear to be essential for an efficient and safe search interaction while driving.