Пододеяльник - это в первую очередь нечто ПОД одеялом, некий кусок ткани/материи между спящим человеком и собственно одеялом. Возможно, одеяла делались из материалов не слишком приятных тактильно (грубая шерсть, например), а потому прямое соприкосновение с ними не способствовало хорошему сну, что сделало появление пододеяльника неизбежным. В отличие от одеяла подушка находится не на человеке, а под ним (ну обычно), а потому кусок ткани/материи должен находится НА подушке в первую очередь. Вполне очевидно, что располагать кусок ткани НА подушке неэффективно, гораздо удобнее сделать что-то вроде мешка. И этот мешок как бы наволакивается на подушку (наволакивается от "волочить"). Поэтому наволочка - это то, что наволакивается. Уже позже пододеяльник из простого куска ткани превратился в мешок, как и наволочка, но названия не сменил=)
А почему пододеяльник-пододеяльник? Если он надодеяльник