Kolja är en vit fisk med en mild smak som liknar torsk som är mycket mångsidig och kan tillagas på flera sätt. Oavsett om den är stekt, bakad eller grillad, sås för kolja kan variera från enkla förberedelser med smör och örter till mer utarbetade pålägg med flera ingredienser. Brun smörsås är en av de enklaste förberedelserna för fisk, som görs genom att smälta smör och låta det bryna långsamt i en kastrull och sedan tillsätta andra önskade ingredienser, som en skvätt balsamvinäger eller färska örter. Sauce nicoise, ett klassiskt franskt tillbehör, kan även användas med kolja och är en blandning av finhackad persilja, svarta oliver och tomater som kan serveras över kolja. En gräddsås för kolja kan också tillagas med ett antal olika smaksättningar.
En koljasås bestående av smält och brynt smör kan vara ett utmärkt komplement till fisken som kommer att framhäva dess smak utan att övermanna den. Den här typen av sås börjar med att långsamt smälta smör i en kastrull på låg till medelhög värme tills det blir gyllenbrunt. Tillagningsprocessen ger smöret en rik, nötaktig smak. Den kan serveras vanlig över kokt kolja, eller ingredienser som färska örter eller vinäger kan läggas till för en starkare smak. Alla beredningar av kolja kan serveras med denna sås.
Sauce nicoise är en annan populär sås för kolja, som kombinerar många olika starka smaker för att bilda en fräsch topping med en konsistens som liknar salsa. Den här såsen görs genom att hacka ingredienser som persilja, nicoise och tomater och dressa dem med olivolja. Andra kryddor, inklusive rosmarin och timjan, tillsätts också ibland, tillsammans med fänkål eller lök. Såsen bör få sitta i minst en timme så att tomaterna kan brytas ner och släppa ut en del av saften. Även om sås nicoise ofta serveras med tonfisk, kan den också användas som en sås till grillad kolja eller annan enkelt tillagad fisk.
Gräddsås är ett annat alternativ med många möjliga varianter. Dessa såser är vanligtvis gjorda av smör, mjöl och tung grädde eller mjölk som basingredienser. Sedan kan vitlök, parmesanost, andra skaldjur som krabba eller örter och kryddor tillsättas. Nästan vilken som helst av dessa kombinationer skulle komplettera stekt, bakad eller grillad fisk. En krabbaköttstoppning för kolja kan göras genom att tillsätta konserverad eller färsk krabba till en vit sås nära slutet av tillagningstiden och sedan hälla den över fisken efter att den har kokats.