Black underlining is the TextEdit default.
Type any text into TextEdit. The font does not matter. Select your text.
From the Format menu : Fonts : Show Fonts (⌘T) — launch the Fonts Panel. On its Toolbar, you will see a button that depicts an underline. Click that button, and select Color from that menu. Select black for your underline, and then revisit the Underline button, and choose Single from the menu. Your selected text now has a black underline. This is also how you would make a red strike-through on black text.
With the text still selected with its now black underline, visit the paragraph styles button (far left) on the Toolbar, and select Show Styles… from its menu. The styles panel will appear with your selection. Click the Add to Favorites button. You will have a panel slide down, where you give your new style a name (e.g. Black underline). I leave the two checkboxes unchecked so that I can apply the style to any font, and I don't care about the ruler. You can experiement here if you want. After you click Add, the new underline style will appear in the Style menu, and can be applied to future text.



Your new style will be persistent across future documents.