> '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)