'Score' is my response variable, and consists of counts, so I'm thinking this represents a Poisson distribution.

That's a reasonable first guess, although you should definitely check for overdispersion (after running the model)

However, I don't think this accounts for any nesting of the data, and again, I'm not sure if that is important here. Also, I'm not sure if 'Day' also needs to be incorporated as a random effect.

I think you're fine. The fact that individuals are nested within species gets take care of automatically. You might want (1) to include variation among individuals in their learning rate, i.e. use (Day|Subject); (2) allow for temporal trends other than (log-)linear, using polynomials (poly()) or splines (splines::ns()) or generalized additive mixed models (gamm4 package).

I also have sex information about all of my subjects ... I assume sex could also be considered as a random effect?

You should probably include sex as a fixed effect, e.g.

Score~Species*Sex*Day + (Day|Subject) 

'Score' is my response variable, and consists of counts, so I'm thinking this represents a Poisson distribution.

That's a reasonable first guess, although you should definitely check for overdispersion (after running the model)

However, I don't think this accounts for any nesting of the data, and again, I'm not sure if that is important here. Also, I'm not sure if 'Day' also needs to be incorporated as a random effect.

I think you're fine. The fact that individuals are nested within species gets taken care of automatically. You might want (1) to include variation among individuals in their learning rate, i.e. use (Day|Subject); (2) allow for temporal trends other than (log-)linear, using polynomials (poly()) or splines (splines::ns()) or generalized additive mixed models (gamm4 package). (Note that I'm assuming here that Day is a numeric variable (continuous covariate), not a factor/categorical variable.)

I also have sex information about all of my subjects ... I assume sex could also be considered as a random effect?

You should probably include sex as a fixed effect, e.g.

Score~Species*Sex*Day + (Day|Subject)