И Шейн хочет в духе времени идти в народ и просвещать его. Ненадолго он становится преподавателем одной из московских воскресных школ, в 1861 году по приглашению Л.Н. Толстого учительствует в Яснополянской школе, затем делается учителем и штатным смотрителем училищ в Туле и Епифани. И всюду он, елико возможно, собирает произведения фольклора, привлекая к сему и своих учеников, и коллег-учителей, и просто случайных знакомых. У него выработалось важное, необходимое фольклористу-профессионалу качество, о чем говорит В.Ф. Миллер: «в разговоре с простым народом Павел Васильевич умел скоро устранять всякие стеснения и заинтересовывать собеседника, напоминал сам ту или другую песню из богатого запаса своей памяти». Необходимо также отметить его участие в деятельности Русского географического общества, с коим он сотрудничал до конца жизни.

За время своего учительства, в переездах из губернии в губернию, он собрал множество народных произведений. Поразительно, что труд сей совершался калекой, которому передвижение и писание давались ценой физических страданий (он не мог даже одеться без посторонней помощи, а влезать и слезать с экипажа стоило ему настоящих мучений). Он еле-еле передвигался на костылях, пальцы сведены от ревматизма, записывать трудно – и при этом Шейн обнаруживает самую завидную энергию. В 1868-1870 годах в «Чтениях Общества истории и древностей российских» выходят собранные Шейном песни детские, хороводные, плясовые, скоморошные, беседные, голосовые или протяжные, шутливые, забавные и сатирические, обрядные, свадебные и похоронные причитания и др. Они издаются и в виде отдельной 600-страничной книги: «Русские народные песни» (Ч. 1. М, 1870), с посвящением «неутомимому деятелю на поприще русского слова» В.И. Далю. Сборник включал около тысячи великорусских песен в принятом собирателем календарно-биографическом порядке. «Везде я старался сближаться с народом, – признается Шейн в предисловии, – прислушиваться к его живой своеобразной речи, пользовался всяким удобным случаем для пополнения своего собрания». Он глубоко убежден, что песня до сих пор «остается верной спутницей многотрудной жизни русского человека от колыбели до могилы», и своим расположением материала стремится раскрыть всю биографию и быт крестьянина в последовательном порядке. Свою задачу он видит в том, чтобы познакомить читателей «очень близко со многими сторонами быта русского человека, с его верованиями… с неисчерпаемым богатством его языка, которым он так творчески умеет пользоваться». И, как отмечали исследователи, «искусным подбором песен Шейну удалось воспроизвести типические черты русского национального характера». Интересно, что одна песня из этого сборника «Спится мне, младешенькой» была включена Н.А. Некрасовым в поэму «Кому на Руси жить хорошо».

Рецензируя книгу, академик Я.К. Грот назвал Шейна одним из «самых ревностных» русских собирателей, подарившим науке сборник песен, «собранных на обширном пространстве великой России»; отмечал его необыкновенную преданность делу и удивительную опытность и сноровку в записывании песен. «По богатству содержания этот том, посвященный В.И. Далю, конечно, порадует всех, интересующихся разработкой русской народной поэзии», – резюмировал Я.К. Грот. А Н.И. Костомаров в статье «Великорусская народная поэзия. По вновь изданным материалам» (1872), так писал о Шейне: «Такое лицо, свято и бескорыстно посвятившее себя прекрасному делу, полезному для отечественной науки, достойно того, чтобы помочь ему, а помочь ему можно только одним – даровать ему средства и содействие к продолжению своего дела.