Best approach for this unsupervised clustering problem with categorical data?
K-means is a reasonable approach and a sensible way to understand the data.
I've never used mahout, but I would use R or Python for this sort of analysis because of the nice libraries available to quickly implement K-means.
The clustering approach with the tags is fairly straightforward. You can essentially encode this using an indicator variable (also known as a binary encoding). You can set this variable/feature to 1 if the tag appeared in the list of tags and 0 otherwise. Then you only need to allocate space for the total number of tags that exist. If you have a large set of tags, you can limit them by taking tags with at least some frequency or some other "sensible" way.
You can choose $k$ in a number of ways. Typically people choose K arbitrarily because they want, e.g., 10 groups to segment their customers or data into. In the simulation I've provided, it'll give you a lame way to optimize for K using an incremental improvement. 


I've made a notebook with a simulation walking you through how to "tokenize" your tags and represent them with a binary/one-hot encoding. It's worth noting that this tokenization ignores the order of the tags, which may be okay for your use case.

It's also worth noting that K-means certainly isn't the only way to measure the similarity of your data but I think it's a nice intuitive start.

Again, for choosing $k$ the approach outlined in the notebook is exhaustive, since it starts from 1 and goes until each observation is a cluster. This means you'll have to run K-means $n$ times, which is silly in practice to do but useful from a learning perspective here. In general, this isn't ideal because it's expensive and typically you don't want to set $k = n$ but this simulation gives nice intuition about what's happening. 

In practice, you can just do it in gaps for a large number of clusters (e.g., 5, 10, 15, 20, .., 100) or something like that and choose the one that has the biggest drop-off by eye-balling it. This is a very arbitrary and unsatisfying way to choose $k$, but it seems to work okay for many people.