Same way you patch any other file.
1) The patch will come as some kind of premade patch designed for something already out in the world. Good old IPS used by most older consoles will not work here as it has a limit of 16 megabytes (give or take a few bytes) and also does not handle reallocations. To that end you will probably have something in the xdelta, ppf or similar regime. Sadly most of those alternatives have multiple versions so you will want to hunt down the right patcher version to match your patch (they tend to be available in the download section here, or easily found in a search), in addition to making sure you have the right version of the bin/cue in the first place*. Most patching programs then amounting to telling it the source file, patch file and then possibly destination file (some will do in place).
2) The patch will come as something aimed at more individual files contained within the filesystem. This will tend to involve you slicing out individual files from the iso and then rebuilding it afterwards.
*I don't know what goes for the megacd side of things here. By the time of the PS1 (not so very long after the rise and fall of the megacd) then CD writers were cheap enough for mortals to afford and it was something of an unofficial contest between CD ripping software (nero with nrg, clonecd, cdrwin... all the formats that the likes of magiciso, ultraiso and the rest claim to handle and more besides) to rip the best PS1 games and dodge any anti piracy involved there. Today then PS1 hackers are faced with supporting legacy iso formats/rips out there for decades at this point or forcing people to rip their own new copy (and hope they have the right version in the case of rereleases with bugfixes), and one of the reasons, most of which are good, 2) above is a thing people do. Megacd being before this and not emulated for a while or probably with much of a Warez/Scene following means you will probably be largely spared that but I note it anyway.
Not knowing what game, what patch and what you have tried already means we are going to struggle to give you more than that.