How do I learn experimental methodology? When is it relevant?
On the metrics. A common technique is to make simulated data with known labels. Then see if your algorithm can reproduce the clustering; if it can't there's a problem, if it can there may still be problems but you're off the starting blocks. Typical measures would include ROC and AUC (essentially how many times does the algo correctly place object i and j in the same class, balanced against false positives).

Another tactic is to use well known real datasets to benchmark against. E.g. the classic iris dataset. See how your algo performs in terms of speed and accuracy versus other algos.

As to what people are looking for this could mean a multitude of things. You might do well to consider where your algo is suited, find an application in that area, and find out whether it performs for that purpose.