Системно — почти никак, потому что полиция и уголовный розыск появятся только в XIX веке, а ранее имели место только совсем уж зачатки подобных органов типа испанской Святой Эрмандады. Хотя бывали креативные решения вроде фемического суда, скажем. Это прямо что-то вроде "баунти хантеров" с Дикого Запада.
Но в основном борьбой с преступностью занимались некие должностные лица по принципу "кто-то же должен решать проблему, займись-ка ты" и неравнодушные граждане. Информацию о разыскиваемых преступниках распространяли, их передача суду (или информации людям, способным его арестовать — какой-нибудь городской страже, обладающему вооружёнными подчинёнными феодалу) сулила некие награды.
Отмечу: с одной стороны розыск сильно усложнялся отсутствием современной паспортизации и фотографий, но с другой — облегчался несравнимо меньшей мобильностью населения в целом (чужак не привлекает внимания разве что в большом порту или крупном торговой узле, а там как раз документы нужны, как правило). Поэтому в целом ловить преступников было вполне реально, хотя серьёзные усилия могли направляться лишь на самых отъявленных (или на самые криминализированные районы).