An iPod shuffle's storage capacity is likely to be far less than the total size of your iTunes music library. Therefore, your iPod shuffle's sync settings are probably NOT set to sync everything in your music library.
Select the iPod shuffle in the iTunes sidebar, under DEVICES. Over to the right, there should be "tabs" that start with Summary. Select the one that says Music. Down below, it should show your current sync settings.
For a shuffle, a convenient way to use syncing is to create one or more playlists specifically for songs you want on the shuffle. Then, set up the syncing (on that Music tab) to sync only those playlists. When you want to add or remove songs from the shuffle, add or remove them from those playlists; the shuffle does not even need to be connected. The next time you connect shuffle, your changes are synced automatically.
This article has more detailed information about syncing iPod shuffle