Assign names to Dataset columns

data = N @ Normalize[#, Total] & @ Counts @ Characters @ ExampleData[
  {"Text", "DeclarationOfIndependence"}
];

Dataset @ data

Dataset[KeyValueMap[<|"char" -> #, "freq" -> #2|> &, data]]

Actully we have a easiest way,suppose you have dataset like

dataset=Dataset[{{"a", 10}, {"b", 11}, {"c", 12}, {"d", 5}, {"e", 99}}]

You can add a column name

dataset[All, <|"char" -> 1, "freq" -> 2|>]

Performance

But if you have a large data set,I have compared FIVE solution here

dataset = Dataset[RandomInteger[100, {200000, 2}]];

AbsoluteTiming[dataset[All, <|"col1" -> 1, "col2" -> 2|>];]
AbsoluteTiming[dataset[Map[AssociationThread[{"col1", "col2"} -> #] &]];]
AbsoluteTiming[dataset[All, Apply[<|"col1" -> #, "col2" -> #2|> &]];]
AbsoluteTiming[dataset[All, Association[Thread[{"col1", "col2"} -> #]] &];]
AbsoluteTiming[dataset[All, AssociationThread[{"col1", "col2"} -> {1, 2}]];]

{2.83872, Null}

{0.968482,Null}

{2.15222, Null}

{1.73927, Null}

{3.03586, Null}

Kuba gave an excellent answer if we can't change the way an original data set is generated. If we can change it, instead of the way it is constructed in the OP, we can do the following:

keys = {"a", "b"};
values = {1, 2};
nameKeys = "keys";
nameValues = "values";
data1 = MapThread[<|nameKeys -> #1, nameValues -> #2|> &, {keys, values}] // Dataset

Just for fun, if we can't change the original data set in the OP and a transformation is needed, we can use the underlying structure and do the low level manipulation:

MapThread[<|nameKeys -> #1, nameValues -> #2|> &, 
          data /. {Association | Rule -> List} // Transpose // Normal] // Dataset