Inspired by the surprising relationship (due to A. Bird) between Schreier sets and the Fibonacci sequence, we introduce Schreier multisets and connect these multisets with the $s$-step Fibonacci sequences, defined, for each $s\geqslant 2$, as: $F^{(s)}_{2-s} = \cdots = F^{(s)}_0 = 0$, $F^{(s)}_1 = 1$, and $F^{(s)}_{n} = F^{(s)}_{n-1} + \cdots + F^{(s)}_{n-s}, \mbox{ for } n\geqslant 2$. Next, we use Schreier-type conditions on multisets to retrieve a family of sequences which satisfy a recurrence of the form $a(n) = a(n-1) + a(n-u)$, with $a(n) = 1$ for $n = 1,\ldots, u$. Finally, we study nonlinear Schreier conditions and show that these conditions are related to integer decompositions, each part of which is greater than the number of parts raised to some power.