git-annex has been around for quite some time, but never really gained momentum.
Git LFS is rather young and is already supported by GitHub, Bitbucket and GitLab.

Both tools handle binary files in git repositories. On the other hand, GitLab seems to have replaced git-annex with Git LFS within one year.

• What are the technical differences?
• Do they solve the same problem?

They do solve the same problem.

Let me start off with pro/con, then I'll move into technical differences.

git-annex

Pros:

• Supports multiple remotes that you can store the binaries.
• Can be used without support from hosting provider (for more details see here).

Cons:

• Windows support in beta, and has been for a long time
• Users need to learn separate commands for day-to-day work
• not supported by github and bitbucket

git-lfs

Pros:

• Supported by github, bitbucket and gitlab
• Most supported on all os's
• Easy to use.
• automated based on filters

Cons:

• Requires a custom server implementation to work. A simple ssh remote is not sufficient. Reference server is under development https://github.com/git-lfs/lfs-test-server.

Technical

git-annex

git-annex works by creating a symlink in your repo that gets committed. The actual data gets stored into a separate backend (S3, rsync, and MANY others). It is written in haskell. Since it uses symlinks, windows users are forced to use annex in a much different manner, which makes the learning curve higher.

git-lfs

Pointer files are written. A git-lfs api is used to write the BLOBs to lfs. A special LFS server is required due to this. Git lfs uses filters so you only have to set up lfs once, and again when you want to specify which types of files you want to push to lfs.