I play both piano and saxophone, and in my experience it is much harder to keep track of the rhythm while playing a wind instrument.
The first thing I would do is write out the counting numbers and clap the rhythms while counting out loud. The subdivisions are very important and, yes, those with good rhythm will keep track of the subdivisions throughout the entire piece. They are necessary for understanding the proportions of the lengths of the different notes. Clapping the rhythm while counting with the subdivisions should help your ear hear the pattern of note lengths. You can add other body movements to help you feel the beat as well, like tapping your toes or nodding your head a little. After clapping out the rhythms a few times, try playing it while counting silently in your head.
Focus on small amounts, a measure or two, at a time. Look at the piece and try to find rhythmic patterns that come back. You will begin to get a sense of how those repeated patterns feel, so you won't have to relearn them each time.
A metronome will come in handy, too, but it is only really useful after you have gotten the hang of counting the subdivisions. Use the feature that will make a special ding on beat one.
A little more about subdivision: How the music is subdivided really depends on what is happening rhythmically in the piece. If the piece's smallest notes are mainly 8th notes, it is really not necessary to count a smaller subdivision than that. The occasional 16th notes can be counted in when you get to them. But if a piece has a lot of 16th notes, it is useful to continually use that subdivision throughout the piece. If a piece has even smaller note values, like 32nd or 64th notes (not beginner pieces!), it is useful to use something smaller than a quarter note to equal the beat and subdivide proportionally from there. Most do not count smaller than four divisions per beat.