"We have dark shoes."
Translation:Nous avons des chaussures sombres.
sombre can be used to describe the overall appearance of colour whereas foncé is generally used in unison with another adjective such as bleu foncé → "dark blue".
soulier is is a somewhat old-fashioned term but it is still widely used in the French fashion industry. Often translated as footwear, it includes things like slippers and sandals, which aren't quite the same as chaussures.